DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.38

Harborth’s Conjecture for 4-Regular Planar Graphs

Authors: Daniel J. Chang and Timothy Sun

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

We show that every 4-regular planar graph has a straight-line embedding in the plane where all edges have integer length. The construction extends earlier ideas for finding such embeddings for 4-regular planar graphs with diamond subgraphs or small edge cuts.

Cite as

Daniel J. Chang and Timothy Sun. Harborth’s Conjecture for 4-Regular Planar Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 38:1-38:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.GD.2024.38,
  author =	{Chang, Daniel J. and Sun, Timothy},
  title =	{{Harborth’s Conjecture for 4-Regular Planar Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{38:1--38:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.38},
  URN =		{urn:nbn:de:0030-drops-213227},
  doi =		{10.4230/LIPIcs.GD.2024.38},
  annote =	{Keywords: Planar graph, straight-line embedding, Diophantine equation}
}

Search Results

Documents authored by Chang, Daniel J.

Harborth’s Conjecture for 4-Regular Planar Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message