fbpx
Wikipedia

Outerplanar graph

April 26, 2024

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

A maximal outerplanar graph and its 3-coloring
The complete graph K4 is the smallest planar graph that is not outerplanar.

Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants. They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2.

The outerplanar graphs are a subset of the planar graphs, the subgraphs of series–parallel graphs, and the circle graphs. The maximal outerplanar graphs, those to which no more edges can be added while preserving outerplanarity, are also chordal graphs and visibility graphs.

History edit

Outerplanar graphs were first studied and named by Chartrand & Harary (1967), in connection with the problem of determining the planarity of graphs formed by using a perfect matching to connect two copies of a base graph (for instance, many of the generalized Petersen graphs are formed in this way from two copies of a cycle graph). As they showed, when the base graph is biconnected, a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a dihedral permutation of its outer cycle. Chartrand and Harary also proved an analogue of Kuratowski's theorem for outerplanar graphs, that a graph is outerplanar if and only if it does not contain a subdivision of one of the two graphs K4 or K2,3.

Definition and characterizations edit

An outerplanar graph is an undirected graph that can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges. Alternatively, a graph G is outerplanar if the graph formed from G by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph.[1]

A maximal outerplanar graph is an outerplanar graph that cannot have any additional edges added to it while preserving outerplanarity. Every maximal outerplanar graph with n vertices has exactly 2n − 3 edges, and every bounded face of a maximal outerplanar graph is a triangle.

Forbidden graphs edit

Outerplanar graphs have a forbidden graph characterization analogous to Kuratowski's theorem and Wagner's theorem for planar graphs: a graph is outerplanar if and only if it does not contain a subdivision of the complete graph K4 or the complete bipartite graph K2,3.[2] Alternatively, a graph is outerplanar if and only if it does not contain K4 or K2,3 as a minor, a graph obtained from it by deleting and contracting edges.[3]

A triangle-free graph is outerplanar if and only if it does not contain a subdivision of K2,3.[4]

Colin de Verdière invariant edit

A graph is outerplanar if and only if its Colin de Verdière graph invariant is at most two. The graphs characterized in a similar way by having Colin de Verdière invariant at most one, three, or four are respectively the linear forests, planar graphs, and linklessly embeddable graphs.

Properties edit

Biconnectivity and Hamiltonicity edit

An outerplanar graph is biconnected if and only if the outer face of the graph forms a simple cycle without repeated vertices. An outerplanar graph is Hamiltonian if and only if it is biconnected; in this case, the outer face forms the unique Hamiltonian cycle.[5] More generally, the size of the longest cycle in an outerplanar graph is the same as the number of vertices in its largest biconnected component. For this reason finding Hamiltonian cycles and longest cycles in outerplanar graphs may be solved in linear time, in contrast to the NP-completeness of these problems for arbitrary graphs.

Every maximal outerplanar graph satisfies a stronger condition than Hamiltonicity: it is node pancyclic, meaning that for every vertex v and every k in the range from three to the number of vertices in the graph, there is a length-k cycle containing v. A cycle of this length may be found by repeatedly removing a triangle that is connected to the rest of the graph by a single edge, such that the removed vertex is not v, until the outer face of the remaining graph has length k.[6]

A planar graph is outerplanar if and only if each of its biconnected components is outerplanar.[4]

Coloring edit

All loopless outerplanar graphs can be colored using only three colors;[7] this fact features prominently in the simplified proof of Chvátal's art gallery theorem by Fisk (1978). A 3-coloring may be found in linear time by a greedy coloring algorithm that removes any vertex of degree at most two, colors the remaining graph recursively, and then adds back the removed vertex with a color different from the colors of its two neighbors.

According to Vizing's theorem, the chromatic index of any graph (the minimum number of colors needed to color its edges so that no two adjacent edges have the same color) is either the maximum degree of any vertex of the graph or one plus the maximum degree. However, in a connected outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a cycle of odd length.[8] An edge coloring with an optimal number of colors can be found in linear time based on a breadth-first traversal of the weak dual tree.[7]

Other properties edit

Outerplanar graphs have degeneracy at most two: every subgraph of an outerplanar graph contains a vertex with degree at most two.[9]

Outerplanar graphs have treewidth at most two, which implies that many graph optimization problems that are NP-complete for arbitrary graphs may be solved in polynomial time by dynamic programming when the input is outerplanar. More generally, k-outerplanar graphs have treewidth O(k).[10]

Every outerplanar graph can be represented as an intersection graph of axis-aligned rectangles in the plane, so outerplanar graphs have boxicity at most two.[11]

Related families of graphs edit

 
A cactus graph. The cacti form a subclass of the outerplanar graphs.

Every outerplanar graph is a planar graph. Every outerplanar graph is also a subgraph of a series–parallel graph.[12] However, not all planar series–parallel graphs are outerplanar. The complete bipartite graph K2,3 is planar and series–parallel but not outerplanar. On the other hand, the complete graph K4 is planar but neither series–parallel nor outerplanar. Every forest and every cactus graph are outerplanar.[13]

The weak planar dual graph of an embedded outerplanar graph (the graph that has a vertex for every bounded face of the embedding, and an edge for every pair of adjacent bounded faces) is a forest, and the weak planar dual of a Halin graph is an outerplanar graph. A planar graph is outerplanar if and only if its weak dual is a forest, and it is Halin if and only if its weak dual is biconnected and outerplanar.[14]

There is a notion of degree of outerplanarity. A 1-outerplanar embedding of a graph is the same as an outerplanar embedding. For k > 1 a planar embedding is said to be k-outerplanar if removing the vertices on the outer face results in a (k − 1)-outerplanar embedding. A graph is k-outerplanar if it has a k-outerplanar embedding.[15]

An outer-1-planar graph, analogously to 1-planar graphs can be drawn in a disk, with the vertices on the boundary of the disk, and with at most one crossing per edge.

Every maximal outerplanar graph is a chordal graph. Every maximal outerplanar graph is the visibility graph of a simple polygon.[16] Maximal outerplanar graphs are also formed as the graphs of polygon triangulations. They are examples of 2-trees, of series–parallel graphs, and of chordal graphs.

Every outerplanar graph is a circle graph, the intersection graph of a set of chords of a circle.[17]

Notes edit

  1. ^ Felsner (2004).
  2. ^ Chartrand & Harary (1967); Sysło (1979); Brandstädt, Le & Spinrad (1999), Proposition 7.3.1, p. 117; Felsner (2004).
  3. ^ Diestel (2000).
  4. ^ a b Sysło (1979).
  5. ^ Chartrand & Harary (1967); Sysło (1979).
  6. ^ Li, Corneil & Mendelsohn (2000), Proposition 2.5.
  7. ^ a b Proskurowski & Sysło (1986).
  8. ^ Fiorini (1975).
  9. ^ Lick & White (1970).
  10. ^ Baker (1994).
  11. ^ Scheinerman (1984); Brandstädt, Le & Spinrad (1999), p. 54.
  12. ^ Brandstädt, Le & Spinrad (1999), p. 174.
  13. ^ Brandstädt, Le & Spinrad (1999), p. 169.
  14. ^ Sysło & Proskurowski (1983).
  15. ^ Kane & Basu (1976); Sysło (1979).
  16. ^ El-Gindy (1985); Lin & Skiena (1995); Brandstädt, Le & Spinrad (1999), Theorem 4.10.3, p. 65.
  17. ^ Wessel & Pöschel (1985); Unger (1988).

References edit

  • Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "The problem of outer embeddings in pseudosurfaces", Ars Combinatoria, 71: 79–91.
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "Obstruction sets for outer-bananas-surface graphs", Ars Combinatoria, 73: 65–77.
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2006), "Uncountable graphs with all their vertices in one face", Acta Mathematica Hungarica, 112 (4): 307–313, doi:10.1007/s10474-006-0082-0, S2CID 123241658.
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2010), "Outer-embeddability in certain pseudosurfaces arising from three spheres", Discrete Mathematics, 310 (23): 3359–3367, doi:10.1016/j.disc.2010.07.027.
  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, ISBN 0-89871-432-X.
  • Chartrand, Gary; Harary, Frank (1967), "Planar permutation graphs", Annales de l'Institut Henri Poincaré B, 3 (4): 433–438, MR 0227041.
  • Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, p. 107, ISBN 0-387-98976-5.
  • El-Gindy, H. (1985), Hierarchical decomposition of polygons with applications, Ph.D. thesis, McGill University. As cited by Brandstädt, Le & Spinrad (1999).
  • Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
  • Fiorini, Stanley (1975), "On the chromatic index of outerplanar graphs", Journal of Combinatorial Theory, Series B, 18 (1): 35–38, doi:10.1016/0095-8956(75)90060-X.
  • Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X.
  • Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society, 38: 215–219, MR 0389672.
  • Kane, Vinay G.; Basu, Sanat K. (1976), "On the depth of a planar graph", Discrete Mathematics, 14 (1): 63–67, doi:10.1016/0012-365X(76)90006-6.
  • Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics, 98 (3): 219–225, doi:10.1016/S0166-218X(99)00163-8.
  • Lick, Don R.; White, Arthur T. (1970), "k-degenerate graphs", Canadian Journal of Mathematics, 22 (5): 1082–1096, doi:10.4153/CJM-1970-125-1, S2CID 124609794.
  • Lin, Yaw-Ling; Skiena, Steven S. (1995), "Complexity aspects of visibility graphs", International Journal of Computational Geometry and Applications, 5 (3): 289–312, doi:10.1142/S0218195995000179.
  • Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Efficient vertex-and edge-coloring of outerplanar graphs", SIAM Journal on Algebraic and Discrete Methods, 7: 131–136, doi:10.1137/0607016.
  • Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of a Graph, Ph.D. thesis, Princeton University. As cited by Brandstädt, Le & Spinrad (1999).
  • Sysło, Maciej M. (1979), "Characterizations of outerplanar graphs", Discrete Mathematics, 26 (1): 47–53, doi:10.1016/0012-365X(79)90060-8.
  • Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
  • Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832.
  • Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, vol. 73, B.G. Teubner, pp. 207–210. As cited by Unger (1988).

External links edit

April 26, 2024
outerplanar, graph, graph, theory, outerplanar, graph, graph, that, planar, drawing, which, vertices, belong, outer, face, drawing, maximal, outerplanar, graph, coloring, complete, graph, smallest, planar, graph, that, outerplanar, characterized, analogously, . In graph theory an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing A maximal outerplanar graph and its 3 coloring The complete graph K4 is the smallest planar graph that is not outerplanar Outerplanar graphs may be characterized analogously to Wagner s theorem for planar graphs by the two forbidden minors K4 and K2 3 or by their Colin de Verdiere graph invariants They have Hamiltonian cycles if and only if they are biconnected in which case the outer face forms the unique Hamiltonian cycle Every outerplanar graph is 3 colorable and has degeneracy and treewidth at most 2 The outerplanar graphs are a subset of the planar graphs the subgraphs of series parallel graphs and the circle graphs The maximal outerplanar graphs those to which no more edges can be added while preserving outerplanarity are also chordal graphs and visibility graphs Contents 1 History 2 Definition and characterizations 2 1 Forbidden graphs 2 2 Colin de Verdiere invariant 3 Properties 3 1 Biconnectivity and Hamiltonicity 3 2 Coloring 3 3 Other properties 4 Related families of graphs 5 Notes 6 References 7 External linksHistory editOuterplanar graphs were first studied and named by Chartrand amp Harary 1967 in connection with the problem of determining the planarity of graphs formed by using a perfect matching to connect two copies of a base graph for instance many of the generalized Petersen graphs are formed in this way from two copies of a cycle graph As they showed when the base graph is biconnected a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a dihedral permutation of its outer cycle Chartrand and Harary also proved an analogue of Kuratowski s theorem for outerplanar graphs that a graph is outerplanar if and only if it does not contain a subdivision of one of the two graphs K4 or K2 3 Definition and characterizations editAn outerplanar graph is an undirected graph that can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing That is no vertex is totally surrounded by edges Alternatively a graph G is outerplanar if the graph formed from G by adding a new vertex with edges connecting it to all the other vertices is a planar graph 1 A maximal outerplanar graph is an outerplanar graph that cannot have any additional edges added to it while preserving outerplanarity Every maximal outerplanar graph with n vertices has exactly 2n 3 edges and every bounded face of a maximal outerplanar graph is a triangle Forbidden graphs edit Outerplanar graphs have a forbidden graph characterization analogous to Kuratowski s theorem and Wagner s theorem for planar graphs a graph is outerplanar if and only if it does not contain a subdivision of the complete graph K4 or the complete bipartite graph K2 3 2 Alternatively a graph is outerplanar if and only if it does not contain K4 or K2 3 as a minor a graph obtained from it by deleting and contracting edges 3 A triangle free graph is outerplanar if and only if it does not contain a subdivision of K2 3 4 Colin de Verdiere invariant edit A graph is outerplanar if and only if its Colin de Verdiere graph invariant is at most two The graphs characterized in a similar way by having Colin de Verdiere invariant at most one three or four are respectively the linear forests planar graphs and linklessly embeddable graphs Properties editBiconnectivity and Hamiltonicity edit An outerplanar graph is biconnected if and only if the outer face of the graph forms a simple cycle without repeated vertices An outerplanar graph is Hamiltonian if and only if it is biconnected in this case the outer face forms the unique Hamiltonian cycle 5 More generally the size of the longest cycle in an outerplanar graph is the same as the number of vertices in its largest biconnected component For this reason finding Hamiltonian cycles and longest cycles in outerplanar graphs may be solved in linear time in contrast to the NP completeness of these problems for arbitrary graphs Every maximal outerplanar graph satisfies a stronger condition than Hamiltonicity it is node pancyclic meaning that for every vertex v and every k in the range from three to the number of vertices in the graph there is a length k cycle containing v A cycle of this length may be found by repeatedly removing a triangle that is connected to the rest of the graph by a single edge such that the removed vertex is not v until the outer face of the remaining graph has length k 6 A planar graph is outerplanar if and only if each of its biconnected components is outerplanar 4 Coloring edit All loopless outerplanar graphs can be colored using only three colors 7 this fact features prominently in the simplified proof of Chvatal s art gallery theorem by Fisk 1978 A 3 coloring may be found in linear time by a greedy coloring algorithm that removes any vertex of degree at most two colors the remaining graph recursively and then adds back the removed vertex with a color different from the colors of its two neighbors According to Vizing s theorem the chromatic index of any graph the minimum number of colors needed to color its edges so that no two adjacent edges have the same color is either the maximum degree of any vertex of the graph or one plus the maximum degree However in a connected outerplanar graph the chromatic index is equal to the maximum degree except when the graph forms a cycle of odd length 8 An edge coloring with an optimal number of colors can be found in linear time based on a breadth first traversal of the weak dual tree 7 Other properties edit Outerplanar graphs have degeneracy at most two every subgraph of an outerplanar graph contains a vertex with degree at most two 9 Outerplanar graphs have treewidth at most two which implies that many graph optimization problems that are NP complete for arbitrary graphs may be solved in polynomial time by dynamic programming when the input is outerplanar More generally k outerplanar graphs have treewidth O k 10 Every outerplanar graph can be represented as an intersection graph of axis aligned rectangles in the plane so outerplanar graphs have boxicity at most two 11 Related families of graphs edit nbsp A cactus graph The cacti form a subclass of the outerplanar graphs Every outerplanar graph is a planar graph Every outerplanar graph is also a subgraph of a series parallel graph 12 However not all planar series parallel graphs are outerplanar The complete bipartite graph K2 3 is planar and series parallel but not outerplanar On the other hand the complete graph K4 is planar but neither series parallel nor outerplanar Every forest and every cactus graph are outerplanar 13 The weak planar dual graph of an embedded outerplanar graph the graph that has a vertex for every bounded face of the embedding and an edge for every pair of adjacent bounded faces is a forest and the weak planar dual of a Halin graph is an outerplanar graph A planar graph is outerplanar if and only if its weak dual is a forest and it is Halin if and only if its weak dual is biconnected and outerplanar 14 There is a notion of degree of outerplanarity A 1 outerplanar embedding of a graph is the same as an outerplanar embedding For k gt 1 a planar embedding is said to be k outerplanar if removing the vertices on the outer face results in a k 1 outerplanar embedding A graph is k outerplanar if it has a k outerplanar embedding 15 An outer 1 planar graph analogously to 1 planar graphs can be drawn in a disk with the vertices on the boundary of the disk and with at most one crossing per edge Every maximal outerplanar graph is a chordal graph Every maximal outerplanar graph is the visibility graph of a simple polygon 16 Maximal outerplanar graphs are also formed as the graphs of polygon triangulations They are examples of 2 trees of series parallel graphs and of chordal graphs Every outerplanar graph is a circle graph the intersection graph of a set of chords of a circle 17 Notes edit Felsner 2004 Chartrand amp Harary 1967 Syslo 1979 Brandstadt Le amp Spinrad 1999 Proposition 7 3 1 p 117 Felsner 2004 Diestel 2000 a b Syslo 1979 Chartrand amp Harary 1967 Syslo 1979 Li Corneil amp Mendelsohn 2000 Proposition 2 5 a b Proskurowski amp Syslo 1986 Fiorini 1975 Lick amp White 1970 Baker 1994 Scheinerman 1984 Brandstadt Le amp Spinrad 1999 p 54 Brandstadt Le amp Spinrad 1999 p 174 Brandstadt Le amp Spinrad 1999 p 169 Syslo amp Proskurowski 1983 Kane amp Basu 1976 Syslo 1979 El Gindy 1985 Lin amp Skiena 1995 Brandstadt Le amp Spinrad 1999 Theorem 4 10 3 p 65 Wessel amp Poschel 1985 Unger 1988 References editBaker Brenda S 1994 Approximation algorithms for NP complete problems on planar graphs Journal of the ACM 41 1 153 180 doi 10 1145 174644 174650 S2CID 9706753 Boza Luis Fedriani Eugenio M Nunez Juan 2004 The problem of outer embeddings in pseudosurfaces Ars Combinatoria 71 79 91 Boza Luis Fedriani Eugenio M Nunez Juan 2004 Obstruction sets for outer bananas surface graphs Ars Combinatoria 73 65 77 Boza Luis Fedriani Eugenio M Nunez Juan 2006 Uncountable graphs with all their vertices in one face Acta Mathematica Hungarica 112 4 307 313 doi 10 1007 s10474 006 0082 0 S2CID 123241658 Boza Luis Fedriani Eugenio M Nunez Juan 2010 Outer embeddability in certain pseudosurfaces arising from three spheres Discrete Mathematics 310 23 3359 3367 doi 10 1016 j disc 2010 07 027 Brandstadt Andreas Le Van Bang Spinrad Jeremy 1999 Graph Classes A Survey SIAM Monographs on Discrete Mathematics and Applications Society for Industrial and Applied Mathematics ISBN 0 89871 432 X Chartrand Gary Harary Frank 1967 Planar permutation graphs Annales de l Institut Henri Poincare B 3 4 433 438 MR 0227041 Diestel Reinhard 2000 Graph Theory Graduate Texts in Mathematics vol 173 Springer Verlag p 107 ISBN 0 387 98976 5 El Gindy H 1985 Hierarchical decomposition of polygons with applications Ph D thesis McGill University As cited by Brandstadt Le amp Spinrad 1999 Felsner Stefan 2004 Geometric graphs and arrangements some chapters from combinational geometry Vieweg Teubner Verlag p 6 ISBN 978 3 528 06972 8 Fiorini Stanley 1975 On the chromatic index of outerplanar graphs Journal of Combinatorial Theory Series B 18 1 35 38 doi 10 1016 0095 8956 75 90060 X Fisk Steve 1978 A short proof of Chvatal s watchman theorem Journal of Combinatorial Theory Series B 24 3 374 doi 10 1016 0095 8956 78 90059 X Fleischner Herbert J Geller D P Harary Frank 1974 Outerplanar graphs and weak duals Journal of the Indian Mathematical Society 38 215 219 MR 0389672 Kane Vinay G Basu Sanat K 1976 On the depth of a planar graph Discrete Mathematics 14 1 63 67 doi 10 1016 0012 365X 76 90006 6 Li Ming Chu Corneil Derek G Mendelsohn Eric 2000 Pancyclicity and NP completeness in planar graphs Discrete Applied Mathematics 98 3 219 225 doi 10 1016 S0166 218X 99 00163 8 Lick Don R White Arthur T 1970 k degenerate graphs Canadian Journal of Mathematics 22 5 1082 1096 doi 10 4153 CJM 1970 125 1 S2CID 124609794 Lin Yaw Ling Skiena Steven S 1995 Complexity aspects of visibility graphs International Journal of Computational Geometry and Applications 5 3 289 312 doi 10 1142 S0218195995000179 Proskurowski Andrzej Syslo Maciej M 1986 Efficient vertex and edge coloring of outerplanar graphs SIAM Journal on Algebraic and Discrete Methods 7 131 136 doi 10 1137 0607016 Scheinerman E R 1984 Intersection Classes and Multiple Intersection Parameters of a Graph Ph D thesis Princeton University As cited by Brandstadt Le amp Spinrad 1999 Syslo Maciej M 1979 Characterizations of outerplanar graphs Discrete Mathematics 26 1 47 53 doi 10 1016 0012 365X 79 90060 8 Syslo Maciej M Proskurowski Andrzej 1983 On Halin graphs Graph Theory Proceedings of a Conference held in Lagow Poland February 10 13 1981 Lecture Notes in Mathematics vol 1018 Springer Verlag pp 248 256 doi 10 1007 BFb0071635 Unger Walter 1988 On the k colouring of circle graphs Proc 5th Symposium on Theoretical Aspects of Computer Science STACS 88 Lecture Notes in Computer Science vol 294 Springer Verlag pp 61 72 doi 10 1007 BFb0035832 Wessel W Poschel R 1985 On circle graphs in Sachs Horst ed Graphs Hypergraphs and Applications Proceedings of the Conference on Graph Theory Held in Eyba October 1st to 5th 1984 Teubner Texte zur Mathematik vol 73 B G Teubner pp 207 210 As cited by Unger 1988 External links editOuterplanar graphs at the Information System on Graph Classes and Their Inclusions Weisstein Eric W Outplanar Graph MathWorld Retrieved from https en wikipedia org w index php title Outerplanar graph amp oldid 1171081130, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.