DROPS

Document

DOI: 10.4230/LIPIcs.GD.2025.26

1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs

Authors: Eliška Červenková and Jan Kratochvíl

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

Matchstick graphs are graphs that allow plane embedding with straight edges of equal length. One-planar unit distance graphs are graphs that allow a drawing in the plane in which all edges are straight-line segments of equal length and every edge crosses at most one other edge. The maximum number of edges of a matchstick graph (1-planar unit distance graph) of order n is denoted by u₀(n) (u₁(n), respectively). It is known that u₀(n) = ⌊ 3n-√{12n-3}⌋ holds for every n. At GD'24, Gehér and Tóth proved a slightly weaker upper bound on u₁(n), but noted that no 1-planar unit distance graph G with more than u₀(|V(G)|) vertices was known. They asked if u₁(n) = u₀(n) holds for every n. We give a negative answer to this question in a much stronger way. We show that u₁(n) > u₀(n) for every n ≥ 16135. Furthermore, we show that the gap between u₁(n) and u₀(n) can be arbitrarily large by proving that for n large enough with respect to a constant α < ∜{1/3}, u₁(n)-u₀(n) ≥ α∜{n}.

Cite as

Eliška Červenková and Jan Kratochvíl. 1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 26:1-26:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cervenkova_et_al:LIPIcs.GD.2025.26,
  author =	{\v{C}ervenkov\'{a}, Eli\v{s}ka and Kratochv{\'\i}l, Jan},
  title =	{{1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{26:1--26:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.26},
  URN =		{urn:nbn:de:0030-drops-250126},
  doi =		{10.4230/LIPIcs.GD.2025.26},
  annote =	{Keywords: planar graph, unit distance graph, matchstick graph, 1-planar graph}
}

Search Results

Documents authored by Červenková, Eliška

1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message