Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Polygon-circle graph
open-in-new
<h2 id="closure-under-induced-minors">Closure under induced minors</h2> <p><a href="/facts/Edge_contraction/PRqKXEkj">Contracting an edge</a> of a polygon-circle graph results in another polygon-circle graph. A geometric representation of the new graph may be formed by replacing the polygons corresponding to the two endpoints of the contracted edge by their <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a>. Alternatively, in the alternating sequence representing the original graph, combining the subsequences representing the endpoints of the contracted edge into a single subsequence produces an alternating sequence representation of the contracted graph. Polygon circle graphs are also closed under <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> or equivalently vertex deletion operations: to delete a vertex, remove its polygon from the geometric representation, or remove its subsequence of points from the alternating sequence. </p> <h2 id="recognition">Recognition</h2> <p>M. Koebe announced a polynomial time recognition algorithm;<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> however, his preliminary version had "serious errors"<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> and a final version was never published.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Martin Pergel later proved that the problem of recognizing these graphs is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> It is also NP-complete to determine whether a given graph can be represented as a polygon-circle graph with at most k vertices per polygon, for any <i>k</i> ≥ 3.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h2 id="related-graph-families">Related graph families</h2> <p>The polygon-circle graphs are a generalization of the <a href="/facts/Circle_graph/mI27LMXp">circle graphs</a>, which are intersection graphs of the chords of a circle, and the <a href="/facts/Trapezoid_graph/I5hNehqD">trapezoid graphs</a>, intersection graphs of trapezoids that all have their vertices on the same two parallel lines. They also include the <a href="/facts/Circular_arc_graph/L3RBxEFs">circular arc graphs</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>Polygon-circle graphs are not, in general, <a href="/facts/Perfect_graph/wcPdhjG9">perfect graphs</a>, but they are near-perfect, in the sense that their <a href="/facts/Chromatic_number/J6HoBfP0">chromatic numbers</a> can be bounded by an (exponential) function of their <a href="/facts/Clique_number/XK9ppLz5">clique numbers</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Kratochvíl, Jan; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 59–70, doi:10.1007/978-3-540-24595-7_6, ISBN 978-3-540-20831-0, MR 2177583. <a href="978-3-540-20831-0" target="_blank">978-3-540-20831-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Koebe, Manfred (1992), "On a new class of intersection graphs", Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), Ann. Discrete Math., vol. 51, North-Holland, Amsterdam, pp. 141–143, doi:10.1016/S0167-5060(08)70618-6, ISBN 978-0-444-89543-1, MR 1206256. <a href="978-0-444-89543-1" target="_blank">978-0-444-89543-1</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Spinrad, Jeremy P. (2003), Efficient graph representations, Fields Institute Monographs, vol. 19, American Mathematical Society, Providence, RI, p. 41, ISBN 0-8218-2815-0, MR 1971502. <a href="0-8218-2815-0" target="_blank">0-8218-2815-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Kratochvíl, Jan; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 59–70, doi:10.1007/978-3-540-24595-7_6, ISBN 978-3-540-20831-0, MR 2177583. <a href="978-3-540-20831-0" target="_blank">978-3-540-20831-0</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Pergel, Martin (2007), "Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete", Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers, Lecture Notes in Computer Science, vol. 4769, Berlin: Springer, pp. 238–247, doi:10.1007/978-3-540-74839-7_23, ISBN 978-3-540-74838-0, MR 2428581. <a href="978-3-540-74838-0" target="_blank">978-3-540-74838-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Kratochvíl, Jan; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 59–70, doi:10.1007/978-3-540-24595-7_6, ISBN 978-3-540-20831-0, MR 2177583. <a href="978-3-540-20831-0" target="_blank">978-3-540-20831-0</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Kratochvíl, Jan; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 59–70, doi:10.1007/978-3-540-24595-7_6, ISBN 978-3-540-20831-0, MR 2177583. <a href="978-3-540-20831-0" target="_blank">978-3-540-20831-0</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Spider graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-07-11. <a href="http://www.graphclasses.org/classes/gc_536.html" target="_blank">http://www.graphclasses.org/classes/gc_536.html</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Kostochka, Alexandr; Kratochvíl, Jan (1997), "Covering and coloring polygon-circle graphs", Discrete Mathematics, 163 (1–3): 299–305, doi:10.1016/S0012-365X(96)00344-5, MR 1428585. <a href="/wiki/Jan_Kratochv%C3%ADl" target="_blank">/wiki/Jan_Kratochv%C3%ADl</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> </ol>