2026-07-24T06:08:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25012 2026-02-09T07:53:33Z ddc:004 open_access

1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs Červenková, Eliška Kratochvíl, Jan planar graph unit distance graph matchstick graph 1-planar graph 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}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eliška Červenková and Jan Kratochvíl 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.26 urn:nbn:de:0030-drops-250126 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode