Results 31 to 40 of about 3,997 (179)
A generalization of outerplanar graphs
Discrete Mathematics, 1984 A graph G is said to be W-outerplanar if it can be embedded in the plane so that all vertices of a given set \(W\subset V(G)\) lie on the boundary of one face. A characterization of such graphs is given by means of forbidden subgraphs, and an algorithm for W-outerplanarity testing is described. The results overlap, in part, with those of \textit{V.
Lía Oubiña, R. Zucchello
openaire +2 more sources
A note on zero-divisor graph of amalgamated duplication of a ring along an ideal
AKCE International Journal of Graphs and Combinatorics, 2017 Let be a commutative ring and be a non-zero ideal of . Let be the subring of consisting of the elements for and . In this paper we characterize all isomorphism classes of finite commutative rings with identity and ideal such that is planar.
A. Mallika, R. Kala
doaj +1 more source
Directed Acyclic Outerplanar Graphs Have Constant Stack Number [PDF]
TheoretiCSThe stack number of a directed acyclic graph $G$ is the minimum $k$ for which there is a topological ordering of $G$ and a $k$-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ...
Paul Jungeblut +2 more
doaj +1 more source
A Note on Edge‐Group Choosability of Planar Graphs without 5‐Cycles
Journal of Mathematics, Volume 2020, Issue 1, 2020., 2020 This paper is devoted to a study of the concept of edge‐group choosability of graphs. We say that G is edge‐k‐group choosable if its line graph is k‐group choosable. In this paper, we study an edge‐group choosability version of Vizing conjecture for planar graphs without 5‐cycles and for planar graphs without noninduced 5‐cycles (2010 Mathematics ...
Amir Khamseh, Andrei V. Kelarev
wiley +1 more source
, 2018 Has appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)
Steven Chaplick +4 more
openaire +2 more sources
A generalization of outerplanar graphs [PDF]
Časopis pro pěstování matematiky, 1988 A planar graph is said to be a generalized outerplanar graph if it has an embedding in the plane in which every edge is incident to a vertex laying on the boundary of the outer face. The author presents a characterization of generalized outerplanar graphs by means of a set of exactly 12 forbidden subgraphs (up to homeomorphism).
openaire +1 more source
On the Order Dimension of Outerplanar Maps [PDF]
Order, 2010 Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset $\Pvef{M}$ of a planar map $M$ is at most four. In this paper we investigate cases where $\dim(\Pvef{M}) \leq 3$ and also where $\dim(\Qvf{M}) \leq 3$; here $\Qvf{M}$ denotes the vertex-face poset of $M$.
Felsner, Stefan, Nilsson, Johan
openaire +3 more sources
The Planar Index and Outerplanar Index of Some Graphs Associated to Commutative Rings
Discussiones Mathematicae - General Algebra and Applications, 2019 In this paper, we study the planar and outerplanar indices of some graphs associated to a commutative ring. We give a full characterization of these graphs with respect to their planar and outerplanar indices when R is a finite ring.
Barati Zahra, Afkhami Mojgan
doaj +1 more source
Nonplanarity of Iterated Line Graphs
Journal of Mathematics, Volume 2020, Issue 1, 2020., 2020 The 1‐crossing index of a graph G is the smallest integer k such that the kth iterated line graph of G has crossing number greater than 1. In this paper, we show that the 1‐crossing index of a graph is either infinite or it is at most 5. Moreover, we give a full characterization of all graphs with respect to their 1‐crossing index.
Jing Wang, Alfred Peris
wiley +1 more source
Algorithms, 2013 The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry.
Takeyuki Tamura, Tatsuya Akutsu
doaj +1 more source