Abstract
Let S be a set of n points in general position in the plane. Together with S we are given a set of parity constraints, that is, every point of S is labeled either even or odd. A graph G on S satisfies the parity constraint of a point \({p\in S}\) if the parity of the degree of p in G matches its label. In this paper, we study how well various classes of planar graphs can satisfy arbitrary parity constraints. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudo-triangulation that satisfy all but at most three parity constraints. For triangulations we can satisfy about 2/3 of the parity constraints and we show that in the worst case there is a linear number of constraints that cannot be fulfilled. In addition, we prove that for a given simple polygon H with polygonal holes on S, it is NP-complete to decide whether there exists a triangulation of H that satisfies all parity constraints.
Similar content being viewed by others
References
Aichholzer, O., Hackl, T., Hoffmann, M., Pilz, A., Rote, G., Speckmann, B., Vogtenhuber, B.: Plane graphs with parity constraints. In: Dehne, F., Munro, I., Sack, J.R., Tamassia, R. (eds.) Algorithms and Data Structures Symposium—WADS 2009. Lecture Notes in Computer Science, Vol. 5664, pp. 13–24. Springer (2009)
Aichholzer O., Hackl T., Huemer C., Hurtado F., Vogtenhuber B.: Large bichromatic point sets admit empty monochromatic 4-gons. SIAM J. Discrete Math. 23(4), 2147–2155 (2010)
Aichholzer, O., Krasser, H.: The point set order type data base: a collection of applications and results. In: Proceedings of the 13th Canadian Conference on Computational Geometry, pp. 17–20. Waterloo, Ontario, Canada (2001)
Alvarez, V.: Even triangulations of planar sets of points with Steiner points. In: Proceedings of the 26th European Workshop on Computational Geometry—EuroCG 2010, pp. 37–40. Dortmund, Germany (2010)
Bose P.: On embedding an outer-planar graph in a point set. Comp. Geom.-Theor. Appl. 23(3), 303–312 (2002)
Bose P., McAllister M., Snoeyink J.: Optimal algorithms to embed trees in a point set. J. Graph Algorithms Appl. 1(2), 1–15 (1997)
Colbourn C., Booth K.: Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10(1), 203–225 (1981)
Erdős P., Gallai T.: Graphs with prescribed degree of vertices. Mat. Lapok 11, 264–274 (1960)
Fernández Delago, I., Grima Ruiz, C.I., Márquez Pérez, A., Nakamoto, A., Robles Arias, R., Valenziela Munõz, J.: Even and quasi-even triangulations of point sets in the plane. In: Proceedings of the 26th European Workshop on Computational Geometry—EuroCG 2010, pp. 161–164. Dortmund, Germany (2010)
Fleischner H.: Gedanken zur Vier-Farben-Vermutung. Monatsh. Math. 79(3), 201–211 (1975)
Gilbert, P.D.: New Results on Planar Triangulations. Master’s thesis, University of Illinois at Urbana-Champaign (1979)
Jansen K.: One strike against the min-max degree triangulation problem. Comp. Geom.-Theor. Appl. 3(2), 107–120 (1993)
Kettner L., Kirkpatrick D., Mantler A., Snoeyink J., Speckmann B., Takeuchi F.: Tight degree bounds for pseudo-triangulations of points. Comp. Geom.-Theor. Appl. 25(1&2), 1–12 (2003)
Klincsek G.T.: Minimal triangulations of polygonal domains. Ann. Discrete Math. 9, 121–123 (1980)
Kooshesh, A., Moret, B.: Folding a triangulated simple polygon: Structural and algorithmic results. In: Dehne, F., Fiala, F., Koczkodaj, W.W. (eds.) Proceedings of the International Conference on Computing and Information, ICCI ’91. Lecture Notes in Computer Science, Vol. 497, pp. 102–110. Springer (1991)
Lichtenstein D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)
Lovász L.: Combinatorial problems and exercises. North-Holland Pub. Co., Amsterdam (1979)
O’Rourke J.: Computational Geometry in C, 2nd edn. Cambridge University Press, New York (1998)
Peláez, C., Ramírez-Vigueras, A., Urrutia, J.: Triangulations with many points of even degree. In: Proceedings of the 22nd Canadian Conference on Computational Geometry—CCCG 2010, pp. 103–106. Winnipeg, Canada (2010)
Pilz, A.: Parity Properties of Geometric Graphs. Master’s thesis, Graz University of Technology, Austria (2009)
Rote, G., Santos, F., Streinu, I.: Pseudo-triangulations—a survey. In: Goodman, E., Pach, J., Pollack, R. (eds.) Surveys on Discrete and Computational Geometry—Twenty Years Later. Contemporary Mathematics, Vol. 453, pp. 343–411. American Mathematical Society, Providence, RI, USA (2008)
Tamura A., Tamura Y.: Degree constrained tree embedding into points in the plane. Inform. Process. Lett. 44, 211–214 (1992)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was initiated during the Fifth European Pseudo-Triangulation Research Week in Ratsch an der Weinstraße, Austria, 2008. Research of O. Aichholzer, T. Hackl, A. Pilz, and B. Vogtenhuber was partially supported by the Austrian Science Fund (FWF): S9205-N12, NFN Industrial Geometry. O. Aichholzer and B. Vogtenhuber are partially supported by the ESF EUROCORES programme EuroGIGA-ComPoSe, Austrian Science Fund (FWF): I 648-N18. T. Hackl is funded by the Austrian Science Fund (FWF): P23629-N18. M. Hoffmann is partially supported by the ESF EUROCORES programme EuroGIGA-GraDr, Swiss National Science Foundation (SNF): 20GG21-134306. A. Pilz is recipient of a DOC-fellowship of the Austrian Academy of Sciences at the Institute for Software Technology, Graz University of Technology, Austria. G. Rote is partially supported by the ESF EUROCORES programme EuroGIGA-ComPoSe, Deutsche Forschungsgemeinschaft (DFG): FE 340/9-1. Research by B. Speckmann supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 639.022.707.
Rights and permissions
About this article
Cite this article
Aichholzer, O., Hackl, T., Hoffmann, M. et al. Plane Graphs with Parity Constraints. Graphs and Combinatorics 30, 47–69 (2014). https://doi.org/10.1007/s00373-012-1247-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-012-1247-y