×

The intersection graph of the disks with diameters the sides of a convex \(n\)-gon. (English) Zbl 1429.05049

Summary: Given a convex polygon of \(n\) sides, one can draw \(n\) disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the \(n\) disks and two disks are adjacent if and only if they have a point in common. We introduce the study of this graph by proving that it is planar for every convex polygon.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)

Software:

GeoGebra
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cabello, S.; Jejčič, M., Refining the hierarchies of classes of geometric intersection graphs, Electron. Notes Discrete Math., 54, 223-228 (2016) · Zbl 1356.05026
[2] Conway, J. H.; Croft, H. T.; Erdős, P.; Guy, M. J.T., On the distribution of values of angles determined by coplanar points, J. Lond. Math. Soc. (2), 19, 1, 137-143 (1979) · Zbl 0414.05006
[3] Danzer, L., Zur Lösung des Gallaischen Problems über Kreisscheiben in der euklidischen Ebene, Stud. Sci. Math. Hung., 21, 111-134 (1986) · Zbl 0626.52007
[4] Fabila-Monroy, R.; Huemer, C.; Tramuns, E., Note on the number of obtuse angles in point sets, Int. J. Comput. Geom. Appl., 24, 03, 177-181 (2014) · Zbl 1331.52023
[5] Hajja, M., A condition for a circumscriptible quadrilateral to be cyclic, Forum Geom., 8, 103-106 (2008) · Zbl 1163.51309
[6] Herrera, L. H.; Pérez-Lantero, P., On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon (2018), arXiv preprint arXiv:1805.10847 · Zbl 1510.05218
[7] Hohenwarter, M., GeoGebra: Ein Softwaresystem für dynamische Geometrie und Algebra der Ebene (2002), Paris Lodron University, Salzburg, Austria, (in German)
[8] C. Huemer, P. Pérez-Lantero, On the disks with diameters the sides of a convex 5-gon, in: XVI Spanish Meeting on Computational Geometry, Barcelona, Spain, July 1-3, 2015, pp. 108-111.
[9] C. Hundack, H. Stamm-Wilbrandt, Planar embedding of hamiltonian graphs via efficient bipartation of circle graphs, University of Bonn, 1994.
[10] Koebe, P., Kontaktprobleme der konformen abbildung, Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88, 141-164 (1936) · Zbl 0017.21701
[11] Kuratowski, C., Sur le probleme des courbes gauches en topologie, Fund. Math., 15, 1, 271-283 (1930) · JFM 56.1141.03
[12] Preparata, F. P., The medial axis of a simple polygon, (Mathematical Foundations of Computer Science 1977. Mathematical Foundations of Computer Science 1977, LNCS, vol. 53 (1977)), 443-450 · Zbl 0361.50003
[13] Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 114, 1, 570-590 (1937) · Zbl 0017.19005
[14] Wenger, R., Helly-type theorems and geometric transversals, (Handbook of Discrete and Comp. Geom. (1997), CRC Press), 63-82, (Chapter 4) · Zbl 0912.52006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.