EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Saturated Partial Embeddings of Planar Graphs

Alexander Clifton, Nika Salia

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →