Scheinerman's conjecture

Scheinerman's conjecture

In mathematics, Scheinerman's conjecture states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane (Ehrlich et al. 1976).

For instance, the graph "G" shown below to the left may be represented as the intersection graph of the set of segments shown below to the right. Here, vertices of "G" are represented by straight line segments and edges of "G" are represented by intersection points.

Scheinerman also conjectured that segments with only three directions would be sufficient to represent 3-colorable graphs, and D. West (1991) conjectured that analogously every planar graph could be represented using four directions. If a graph is represented with segments having only "k" directionsand no two segments belong to the same line, then the graph can be colored using "k" colors, one color for each direction. Therefore, if every planar graph can be represented in this way with only four directions,then the four color theorem follows.

Hartman et al. (1991) and de Fraisseix et al. (1991) proved that every bipartite planar graph can be represented as an intersection graph of horizontal and vertical line segments; for this result see also Czyzowicz et al (1998). De Castro et al. (2002) proved that every triangle-free planar graph can be represented as an intersection graph of line segments having only three directions; this result implies Grötzsch's theorem (Grötzsch 1959) that triangle-free planar graphs can be colored with three colors. De Fraysseix and Ossona de Mendez (2005) proved that if a planar graph "G" can be 4-colored in such a way that no separating cycle uses all four colors, then "G" has a representation as an intersection graph of segments.

Chalopin et al. (2007) proved that planar graphs are in 1-STRING, the class of intersection graphs of simple curves in the plane that intersect each other in at most one crossing point per pair. This class is intermediate between the intersection graphs of segments appearing in Scheinerman's conjecture and the intersection graphs of unrestricted simple curves from the result of Ehrlich et al.

References

*cite journal
author = de Castro, N.; Cobos, F. J.; Dana, J. C.; Márquez, A.
title = Triangle-free planar graphs as segment intersection graphs
journal = Journal of Graph Algorithms and Applications
volume = 6
year = 2002
issue = 1
pages = 7–26
id = MathSciNet | id = 1898201
url = http://www.cs.brown.edu/publications/jgaa/accepted/2002/deCastro+2002.6.1.pdf

*cite conference
author = Chalopin, J.; Gonçalves, D.; Ochem, P.
title = Planar graphs are in 1-STRING
booktitle = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms
publisher = ACM and SIAM
year = 2007
pages = 609–617

*cite journal
author = Czyzowicz, J.; Kranakis, E.; Urrutia, J.
title = A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments
journal = Information Processing Letters
volume = 66
issue = 3
year = 1998
pages = 125–126
doi = 10.1016/S0020-0190(98)00046-5

*cite conference
author = de Fraysseix, H.; Ossona de Mendez, P.
title = Contact and intersection representations
editor = J. Pach (Ed.)
booktitle = Graph Drawing, 12th International Symposium, GD 2004
publisher = Lecture Notes in Computer Science, vol. 3383, Springer-Verlag
pages = 217–227
date = 2005

*cite journal
author = de Fraysseix, H.; Ossona de Mendez, P.; Pach, J.
title = Representation of planar graphs by segments
journal = Intuitive Geometry
volume = 63
year = 1991
pages = 109–117
id = MathSciNet | id = 1383616

*cite journal
author = Ehrlich, G.; Even, S.; Tarjan, R. E.
title = Intersection graphs of curves in the plane
journal = Journal of Combinatorial Theory, Series B
volume = 21
pages = 8–20
year = 1976
issue = 1
id = MathSciNet | id = 0505857
doi = 10.1016/0095-8956(76)90022-8

*cite journal
author = Grötzsch, Herbert
title = Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel
journal = Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe
volume = 8
year = 1959
pages = 109–120
id = MathSciNet | id = 0116320

*cite journal
author = Hartman, I. B.-A.; Newman, I.; Ziv, R.
title = On grid intersection graphs
journal = Discrete Mathematics
volume = 87
issue = 1
year = 1991
pages = 41–52
id = MathSciNet | id = 1090188
doi = 10.1016/0012-365X(91)90069-E

*cite paper
author = Scheinerman, E. R.
title = Intersection classes and multiple intersection parameters of graphs
version = Ph.D. thesis
publisher = Princeton University
date = 1984

*cite journal
author = West, D.
title = Open problems
journal = SIAM J. Discrete Math. Newslett.
volume = 2
year = 1991
issue = 1
pages = 10–12


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Intersection graph — In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may… …   Wikipedia

  • String graph — In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a string . Given a graph G , G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three… …   Wikipedia

  • Circle packing theorem — Example of the circle packing theorem on K5, the complete graph on five vertices, minus one edge. The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane …   Wikipedia

  • Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia

  • Happy Ending problem — The Happy Ending problem (so named by Paul Erdős since it led to the marriage of George Szekeres and Esther Klein) is the following statement::Theorem. Any set of five points in the plane in general position [In this context, general position… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”