Saturated Partial Embeddings of Planar Graphs
Journal of Graph Theory · 07.08.2026
DOI: 10.1002/jgt.70109 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 07.08.2026. Verfasst von Alexander Clifton und 1 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Institute for Basic Science, Grantová Agentura České Republiky.
Abstract (Originalsprache)
In this work, we study how far one can deviate from optimal behavior when embedding a planar graph. For a planar graph , we say that a plane subgraph is a plane‐saturated subgraph if adding any edge (possibly with new vertices) to would either violate planarity or make the resulting graph no longer a subgraph of . For a planar graph , we define the plane‐saturation ratio , , as the minimum value of for a plane‐saturated subgraph of and investigate how small can be. While there exist planar graphs where is arbitrarily close to 0, we show that for all twin‐free planar graphs, , and that there exist twin‐free planar graphs where is arbitrarily close to 1/16. We study a broader category of planar graphs, focusing on classes characterized by a bounded number of degree 1 and degree 2 twin vertices. We offer solutions for some instances of bounds while positing conjectures for the remaining ones.
Förderung
- Institute for Basic Science
- Grantová Agentura České Republiky
Zitieren
APA
Clifton, A., & Salia, N. (2026). Saturated Partial Embeddings of Planar Graphs. Journal of Graph Theory. https://doi.org/10.1002/jgt.70109
Vancouver
Clifton A, Salia N. Saturated Partial Embeddings of Planar Graphs. Journal of Graph Theory. 2026. doi:10.1002/jgt.70109
BibTeX
@article{Clifton2026,
author = {Clifton, Alexander and Salia, Nika},
title = {Saturated Partial Embeddings of Planar Graphs},
journal = {Journal of Graph Theory},
year = {2026},
doi = {10.1002/jgt.70109}
}
EUVIMED