On the edge crossing properties of Euclidean minimum weight Laman graphs

DOI10.1016/j.comgeo.2015.10.002zbMath1329.05076OpenAlexW2191793880WikidataQ62041717 ScholiaQ62041717MaRDI QIDQ902420

Naoki Katoh, Seok-Hee Hong, Sheung-Hung Poon, Sergey Bereg, Shin-ichi Tanigawa

Publication date: 18 January 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2015.10.002

zbMATH Keywords

plane graphsLaman graphs\((k, l)\)-sparse graphs\(k\)-planarityquasi-planarity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Density (toughness, etc.) (05C42)

Related Items

Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• On crossing numbers of geometric proximity graphs
• Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Graphs drawn with few crossings per edge
• Quasi-planar graphs have a linear number of edges
• Algorithms for graphs embeddable with few crossings per edge
• Pebble game algorithms and sparse graphs
• On graphs and rigidity of plane skeletal structures
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• The Number of Edges in $k$-Quasi-planar Graphs