Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Scheinermans_conjecture> ?p ?o }
Showing triples 1 to 55 of
55
with 100 triples per page.
- Scheinermans_conjecture abstract "In mathematics, Scheinerman's conjecture, now a theorem, 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, Even & Tarjan 1976). It was proven by Jeremie Chalopin and Daniel Gonçalves (2009).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 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, Newman & Ziv (1991) and de Fraysseix, Ossona de Mendez & Pach (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, Kranakis & Urrutia (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 & 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, Gonçalves & Ochem (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. It can also be viewed as a generalization of the circle packing theorem, which shows the same result when curves are allowed to intersect in a tangent. The proof of the conjecture by Chalopin & Gonçalves (2009) was based on an improvement of this result.".
- Scheinermans_conjecture thumbnail Intersect1.png?width=300.
- Scheinermans_conjecture wikiPageExternalLink deCastro+2002.6.1.pdf.
- Scheinermans_conjecture wikiPageExternalLink ChalopinG09.pdf.
- Scheinermans_conjecture wikiPageID "3125930".
- Scheinermans_conjecture wikiPageLength "7114".
- Scheinermans_conjecture wikiPageOutDegree "23".
- Scheinermans_conjecture wikiPageRevisionID "681976649".
- Scheinermans_conjecture wikiPageWikiLink Bipartite_graph.
- Scheinermans_conjecture wikiPageWikiLink Category:Conjectures.
- Scheinermans_conjecture wikiPageWikiLink Category:Planar_graphs.
- Scheinermans_conjecture wikiPageWikiLink Circle_packing_theorem.
- Scheinermans_conjecture wikiPageWikiLink Ed_Scheinerman.
- Scheinermans_conjecture wikiPageWikiLink Four_color_theorem.
- Scheinermans_conjecture wikiPageWikiLink Graph_coloring.
- Scheinermans_conjecture wikiPageWikiLink Graph_theory.
- Scheinermans_conjecture wikiPageWikiLink Grxc3xb6tzschs_theorem.
- Scheinermans_conjecture wikiPageWikiLink Information_Processing_Letters.
- Scheinermans_conjecture wikiPageWikiLink International_Symposium_on_Graph_Drawing.
- Scheinermans_conjecture wikiPageWikiLink Intersection_graph.
- Scheinermans_conjecture wikiPageWikiLink Journal_of_Combinatorial_Theory.
- Scheinermans_conjecture wikiPageWikiLink Journal_of_Graph_Algorithms_and_Applications.
- Scheinermans_conjecture wikiPageWikiLink Line_segment.
- Scheinermans_conjecture wikiPageWikiLink Mathematics.
- Scheinermans_conjecture wikiPageWikiLink Planar_graph.
- Scheinermans_conjecture wikiPageWikiLink String_graph.
- Scheinermans_conjecture wikiPageWikiLink Symposium_on_Theory_of_Computing.
- Scheinermans_conjecture wikiPageWikiLink Triangle-free_graph.
- Scheinermans_conjecture wikiPageWikiLink Vertex_(graph_theory).
- Scheinermans_conjecture wikiPageWikiLink File:Intersect1.png.
- Scheinermans_conjecture wikiPageWikiLink File:Intersect2.png.
- Scheinermans_conjecture wikiPageWikiLinkText "Scheinerman's conjecture".
- Scheinermans_conjecture first "Daniel".
- Scheinermans_conjecture first "Jeremie".
- Scheinermans_conjecture hasPhotoCollection Scheinermans_conjecture.
- Scheinermans_conjecture last "Chalopin".
- Scheinermans_conjecture last "Gonçalves".
- Scheinermans_conjecture wikiPageUsesTemplate Template:Citation.
- Scheinermans_conjecture wikiPageUsesTemplate Template:Harv.
- Scheinermans_conjecture wikiPageUsesTemplate Template:Harvid.
- Scheinermans_conjecture wikiPageUsesTemplate Template:Harvs.
- Scheinermans_conjecture wikiPageUsesTemplate Template:Harvtxt.
- Scheinermans_conjecture year "2009".
- Scheinermans_conjecture subject Category:Conjectures.
- Scheinermans_conjecture subject Category:Planar_graphs.
- Scheinermans_conjecture hypernym Graph.
- Scheinermans_conjecture type Software.
- Scheinermans_conjecture comment "In mathematics, Scheinerman's conjecture, now a theorem, 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, Even & Tarjan 1976).".
- Scheinermans_conjecture label "Scheinerman's conjecture".
- Scheinermans_conjecture sameAs m.08t3g6.
- Scheinermans_conjecture sameAs Q7431096.
- Scheinermans_conjecture sameAs Q7431096.
- Scheinermans_conjecture wasDerivedFrom Scheinermans_conjectureoldid=681976649.
- Scheinermans_conjecture depiction Intersect1.png.
- Scheinermans_conjecture isPrimaryTopicOf Scheinermans_conjecture.