DROPS

Document

DOI: 10.4230/LIPIcs.GD.2024.6

1-Planar Unit Distance Graphs

Authors: Panna Gehér and Géza Tóth

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

Abstract

A matchstick graph is a plane graph with edges drawn as unit distance line segments. This class of graphs was introduced by Harborth who conjectured that a matchstick graph on n vertices can have at most ⌊3n-√{12n-3}⌋ edges. Recently his conjecture was settled by Lavollée and Swanepoel. In this paper we consider 1-planar unit distance graphs. We say that a graph is a 1-planar unit distance graph if it can be drawn in the plane such that all edges are drawn as unit distance line segments while each of them are involved in at most one crossing. We show that such graphs on n vertices can have at most 3n-∜{n}/10 edges.

Cite as

Panna Gehér and Géza Tóth. 1-Planar Unit Distance Graphs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 6:1-6:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{geher_et_al:LIPIcs.GD.2024.6,
  author =	{Geh\'{e}r, Panna and T\'{o}th, G\'{e}za},
  title =	{{1-Planar Unit Distance Graphs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-212900},
  doi =		{10.4230/LIPIcs.GD.2024.6},
  annote =	{Keywords: unit distance graph, 1-planar, matchstick graph}
}

Search Results

Documents authored by Gehér, Panna

1-Planar Unit Distance Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message