Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Face-hitting dominat ...
Article

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm

Therese Biedl ORCID (1)
(1) University of Waterloo [UW]
Download article
Open on arXiv
Submitted on
March 17, 2026
Accepted on
July 1, 2026
Published on
August 17, 2026
Last modified on
August 17, 2026
Special issue 28
vol. 28:4, SOFSEM 2026
Special issues
DOI
10.46298/dmtcs.17747
License
Attribution 4.0 International (CC BY 4.0)
Indicators
115
Views
70
Downloads

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm

Therese Biedl ORCID (1)
(1) University of Waterloo [UW]
Abstract
In a recent paper, Francis, Illickan, Jose and Rajendraprasad showed that every $n$-vertex plane graph $G$ has (under some natural restrictions) a vertex-partition into two sets $V_1$ and $V_2$ such that each $V_i$ is \emph{dominating} (every vertex of $G$ contains a vertex of $V_i$ in its closed neighbourhood) and \emph{face-hitting} (every face of $G$ is incident to a vertex of $V_i$). Their proof works by considering a supergraph $G'$ of $G$ that has certain properties, and among all such graphs, taking one that has the fewest edges. As such, their proof is not algorithmic. Their proof also relies on the 4-color theorem, for which a quadratic-time algorithm exists, but it would not be easy to implement. In this paper, we give a new proof that every $n$-vertex plane graph $G$ has (under the same restrictions) a vertex-partition into two dominating face-hitting sets. Our proof is constructive, and requires nothing more complicated than splitting a graph into 2-connected components, finding an ear decomposition, and computing a perfect matching in a 3-regular plane graph. For all these problems, linear-time algorithms are known and so we can find the vertex-partition in linear time. Preliminary version appeared at SOFSEM 2026
Keywords
  • Data Structures and Algorithms
  • Combinatorics
Preview
Loading PDF preview...
References

  1. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1): 153-180, 1994.

    DOI : 10.1145/174644.174650

  2. Marshall W. Bern, Herbert Edelsbrunner, David Eppstein, Scott A. Mitchell, and Tiow Seng Tan. Edge insertion for optimal triangulations. Discret. Comput. Geom., 10:47-65, 1993.

    DOI : 10.1007/bf02573962

  3. Therese Biedl and Dana F. Wilkinson. Bounded-degree independent sets in planar graphs. Theory Comput. Syst., 38(3):253-278, 2005.

    DOI : 10.1007/s00224-005-1139-0

  4. Therese Biedl, Goos Kant, and Michael Kaufmann. On triangulating planar graphs under the four- connectivity constraint. Algorithmica, 19(4):427-446, 1997.

    DOI : 10.1007/pl00009182

  5. Therese Biedl, Prosenjit Bose, Erik D. Demaine, and Anna Lubiw. Efficient algorithms for Petersen's matching theorem. J. Algorithms, 38(1):110-134, 2001.

    DOI : 10.1006/jagm.2000.1132

  6. Prosenjit Bose, David G. Kirkpatrick, and Zaiqing Li. Efficient algorithms for guarding or illuminating the surface of a polyhedral terrain. In Frank Fiala, Evangelos Kranakis, and Jörg-Rüdiger Sack, editors, Canadian Conference on Computational Geometry, pages 217-222. Carleton University Press, 1996.

    DOI : 10.1515/9780773591134-039

  7. Prosenjit Bose, Thomas C. Shermer, Godfried T. Toussaint, and Binhai Zhu. Guarding polyhedral terrains. Comput. Geom., 7:173-185, 1997.

    DOI : 10.1016/0925-7721(95)00034-8

  8. Aleksander B. G. Christiansen, Eva Rotenberg, and Daniel Rutschmann. Triangulations admit dominating sets of size 2n/7. In David P. Woodruff, editor, ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 1194-1240. SIAM, 2024.

    DOI : 10.1137/1.9781611977912.47

  9. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. ISBN 978-3-642-14278-9.

    DOI : 10.1137/1.9781611977912.47

  10. William S. Evans, Ellen Gethner, Jack Spalding-Jamieson, and Alexander Wolff. Angle covers: Algo- rithms and complexity. J. Graph Algorithms Appl., 25(2):643-661, 2021.

    DOI : 10.7155/jgaa.00576

  11. Shimon Even and Robert Endre Tarjan. Computing an st-numbering. Theor. Comput. Sci., 2(3):339-344, 1976.

    DOI : 10.1016/0304-3975(76)90086-4

  12. P. Francis, Abraham M. Illickan, Lijo M. Jose, and Deepak Rajendraprasad. Face-hitting dominating sets in planar graphs. In Daniel Král and Martin Milanic, editors, International Workshop on Graph- Theoretic Concepts in Computer Science, WG 2024, Lecture Notes in Computer Science, pages 211- 219. Springer, 2024.

    DOI : 10.1007/978-3-031-75409-8_15

  13. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.

  14. John E. Hopcroft and Robert Endre Tarjan. Efficient algorithms for graph manipulation [H] (algorithm 447). Commun. ACM, 16(6):372-378, 1973.

    DOI : 10.1145/362248.362272

  15. Goos Kant and Hans L. Bodlaender. Triangulating planar graphs while minimizing the maximum degree. Inf. Comput., 135(1):1-14, 1997.

    DOI : 10.1006/inco.1997.2635

  16. Abraham Lempel, Shimon Even, and Israel Cederbaum. An algorithm for planarity testing of graphs. In Pierre Rosenstiehl, editor, Theory of Graphs, International Symposium Rome 1966, pages 215-232. Gordon and Breach, 1967.

  17. Lesley R. Matheson and Robert Endre Tarjan. Dominating sets in planar graphs. Eur. J. Comb., 17(6): 565-568, 1996.

    DOI : 10.1006/eujc.1996.0048

  18. Julius Petersen. Die Theorie der regulären graphs (The theory of regular graphs). Acta Mathematica, 15: 193-220, 1891.

    DOI : 10.1007/bf02392606

  19. Neil Robertson, Daniel P. Sanders, Paul D. Seymour, and Robin Thomas. The four-colour theorem. J. Comb. Theory B, 70(1):2-44, 1997.

    DOI : 10.1006/jctb.1997.1750

  20. Pierre Rosenstiehl and Robert Endre Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discret. Comput. Geom., 1:343-353, 1986.

    DOI : 10.1007/BF02187706

  21. Roberto Tamassia and Ioannis G. Tollis. A unified approach a visibility representation of planar graphs. Discret. Comput. Geom., 1:321-341, 1986.

    DOI : 10.1007/bf02187705

  22. Hassler Whitney. Non-separable and planar graphs. Proceedings of the National Academy of Sciences, 17(2):125-127, 1931.

    DOI : 10.1073/pnas.17.2.125