Back to Search
Start Over
Every planar graph is the intersection graph of segments in the plane
- Source :
- STOC, STOC '09: 41st ACM Symposium on Theory of Computing, STOC '09: 41st ACM Symposium on Theory of Computing, May 2009, France. pp.631-638
- Publication Year :
- 2009
- Publisher :
- ACM, 2009.
-
Abstract
- International audience; Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton\nUniversity, 1984) that every planar graph is the intersection graph of some segments in the plane.
- Subjects :
- Discrete mathematics
Planar straight-line graph
Intersection graph
intersection graphs
planar graphs
Geometric graph theory
law.invention
Planar graph
Combinatorics
symbols.namesake
law
Outerplanar graph
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
String graph
symbols
Circle graph
Complement graph
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the forty-first annual ACM symposium on Theory of computing
- Accession number :
- edsair.doi.dedup.....94c8e3455fd59a4c72d2a3c082693617
- Full Text :
- https://doi.org/10.1145/1536414.1536500