Jump to content

Polygon-circle graph: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Bremby (talk | contribs)
Created page with 'Polygon-circle graph is a type of an intersection graph, where each vertex is represented as a polygon and edge as an intersection of two polygons represent...'
 
Citation bot (talk | contribs)
Alter: url, issue. URLs might have been anonymized. Added isbn. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:NP-complete problems | #UCB_Category 41/181
 
(23 intermediate revisions by 16 users not shown)
Line 1: Line 1:
{{Short description|Intersection graph of convex polygons whose vertices lie on a common circle}}
Polygon-circle graph is a type of an [[intersection graph]], where each vertex is represented as a [[polygon]] and edge as an intersection of two polygons representing those vertices, enclosed by a bounding circle. All corners of all polygons lie on the bounding circle. They were first suggested by [[Michael Fellows]] in 1988.
{{redirect|Spider graph|the chart|radar chart|the cricket term|Glossary of cricket terms}}


Polygon-circle graph can be represented as "alternating sequence". Such sequence can be gained by cutting the bounding circle in an arbitrary point and listing the polygons, as we go along. Such sequence is unique.
[[File:Polygon-circle graph.svg|thumb|right|400px|{{center|On the left a set of polygons inscribed in a circle; on the right the relative '''Polygon-circle graph''' (intersection graph of the polygons).<br> On the bottom the alternating sequence of polygons around the circle.}}]]


In the [[mathematics|mathematical]] discipline of [[graph theory]], a '''polygon-circle graph''' is an [[intersection graph]] of a set of [[convex polygon]]s all of whose [[vertex (geometry)|vertices]] lie on a common circle. These graphs have also been called '''spider graphs'''. This class of graphs was first suggested by [[Michael Fellows]] in 1988, motivated by the fact that it is closed under [[edge contraction]] and [[induced subgraph]] operations.<ref name="kp">{{citation
They can also be referred to as "spider graphs".
| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl
| last2 = Pergel | first2 = Martin
| contribution = Two results on intersection graphs of polygons
| doi = 10.1007/978-3-540-24595-7_6
| mr = 2177583
| pages = 59–70
| publisher = Springer | location = Berlin
| series = Lecture Notes in Computer Science
| title = [[International Symposium on Graph Drawing|Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers]]
| volume = 2912
| year = 2004| doi-access = free
| isbn = 978-3-540-20831-0 }}.</ref>

A polygon-circle graph can be represented as an "alternating sequence". Such a sequence can be gained by perturbing the polygons representing the graph (if necessary) so that no two share a vertex, and then listing for each vertex (in circular order, starting at an arbitrary point) the polygon attached to that vertex.

==Closure under induced minors==
[[Edge contraction|Contracting an edge]] 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 [[convex hull]]. 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 [[induced subgraph]] 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.


==Recognition==
==Recognition==
M. Koebe announced a polynomial time recognition algorithm;<ref>{{citation
M. Koebe announced polynomial time recognition algorithm<ref>M. Koebe. ''On a new class of intersection graphs'' in Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice, pages 141 - 143, 1990.</ref>, but it was never published. Algorithm was first published by M. Pergel and J. Kratochvíl<ref>M. Pergel. ''Special Graph Classes and Algorithms on Them''. Doctoral Thesis, 2007.</ref>.
| last = Koebe | first = Manfred
| contribution = On a new class of intersection graphs
| doi = 10.1016/S0167-5060(08)70618-6
| mr = 1206256
| pages = 141–143
| publisher = North-Holland, Amsterdam
| series = Ann. Discrete Math.
| title = Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990)
| volume = 51
| year = 1992| isbn = 978-0-444-89543-1
}}.</ref> however, his preliminary version had "serious errors"<ref>{{citation
| last = Spinrad | first = Jeremy P.
| isbn = 0-8218-2815-0
| mr = 1971502
| page = 41
| publisher = American Mathematical Society, Providence, RI
| series = Fields Institute Monographs
| title = Efficient graph representations
| url = https://books.google.com/books?id=RrtXSKMAmWgC&pg=PA41
| volume = 19
| year = 2003}}.</ref> and a final version was never published.<ref name="kp"/> Martin Pergel later proved that the problem of recognizing these graphs is [[NP-complete]].<ref>{{citation
| last = Pergel | first = Martin
| contribution = Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete
| doi = 10.1007/978-3-540-74839-7_23
| mr = 2428581
| pages = 238–247
| publisher = Springer | location = Berlin
| series = Lecture Notes in Computer Science
| title = Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers
| volume = 4769
| year = 2007| isbn = 978-3-540-74838-0
}}.</ref>
It is also NP-complete to determine whether a given graph can be represented as a polygon-circle graph with at most {{mvar|k}} vertices per polygon, for any {{math|''k'' ≥ 3}}.<ref name="kp"/>


==Related graph families==
The polygon-circle graphs are a generalization of the [[circle graph]]s, which are intersection graphs of the chords of a circle, and the [[trapezoid graph]]s, intersection graphs of trapezoids that all have their vertices on the same two parallel lines. They also include the [[circular arc graph]]s.<ref name="kp"/><ref>[http://www.graphclasses.org/classes/gc_536.html Spider graphs], Information System on Graph Classes and their Inclusions, retrieved 2016-07-11.</ref>


Polygon-circle graphs are not, in general, [[perfect graph]]s, but they are near-perfect, in the sense that their [[chromatic number]]s can be bounded by an (exponential) function of their [[clique number]]s.<ref>{{citation
| last1 = Kostochka | first1 = Alexandr
| last2 = Kratochvíl | first2 = Jan | author2-link = Jan Kratochvíl
| doi = 10.1016/S0012-365X(96)00344-5
| issue = 1–3
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| mr = 1428585
| pages = 299–305
| title = Covering and coloring polygon-circle graphs
| volume = 163
| year = 1997| doi-access = free
}}.</ref>


==References==
==References==
{{reflist}}
<references/>


[[Category:Intersection classes of graphs]]
* J. P. Spinrad. ''Efficient Graph Representations''. American Mathematical Society, 2003.
[[Category:NP-complete problems]]

Latest revision as of 11:46, 12 August 2024

On the left a set of polygons inscribed in a circle; on the right the relative Polygon-circle graph (intersection graph of the polygons).
On the bottom the alternating sequence of polygons around the circle.

In the mathematical discipline of graph theory, a polygon-circle graph is an intersection graph of a set of convex polygons all of whose vertices lie on a common circle. These graphs have also been called spider graphs. This class of graphs was first suggested by Michael Fellows in 1988, motivated by the fact that it is closed under edge contraction and induced subgraph operations.[1]

A polygon-circle graph can be represented as an "alternating sequence". Such a sequence can be gained by perturbing the polygons representing the graph (if necessary) so that no two share a vertex, and then listing for each vertex (in circular order, starting at an arbitrary point) the polygon attached to that vertex.

Closure under induced minors

[edit]

Contracting an edge 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 convex hull. 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 induced subgraph 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.

Recognition

[edit]

M. Koebe announced a polynomial time recognition algorithm;[2] however, his preliminary version had "serious errors"[3] and a final version was never published.[1] Martin Pergel later proved that the problem of recognizing these graphs is NP-complete.[4] 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 k ≥ 3.[1]

[edit]

The polygon-circle graphs are a generalization of the circle graphs, which are intersection graphs of the chords of a circle, and the trapezoid graphs, intersection graphs of trapezoids that all have their vertices on the same two parallel lines. They also include the circular arc graphs.[1][5]

Polygon-circle graphs are not, in general, perfect graphs, but they are near-perfect, in the sense that their chromatic numbers can be bounded by an (exponential) function of their clique numbers.[6]

References

[edit]
  1. ^ a b c d 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.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ Spider graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-07-11.
  6. ^ 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.