Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs

DOI10.7155/jgaa.00463zbMath1398.05109OpenAlexW3098926989WikidataQ130064870 ScholiaQ130064870MaRDI QIDQ4961756

David Eppstein

Publication date: 25 October 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00463

zbMATH Keywords

graph drawingdegeneracy of an undirected graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (1)

Bounding the Number of Edges of Matchstick Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Densities of minor-closed graph families
• On the maximum number of edges in quasi-planar graphs
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• Colorings and orientations of graphs
• Graphs drawn with few crossings per edge
• On the independence number of minimum distance graphs
• The logic engine and the realization problem for nearest neighbor graphs
• Quasi-planar graphs have a linear number of edges
• A short list color proof of Grötzsch's theorem
• A not 3-choosable planar graph without 3-cycles
• Optimal Angular Resolution for Face-Symmetric Drawings
• Combinatorial Properties of Triangle-Free Rectangle Arrangements and the Squarability Problem
• Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
• 3-Choosability of Triangle-Free Planar Graphs with Constraints on 4-Cycles
• Combinatorics and Geometry of Finite and Infinite Squaregraphs
• Contact Graphs of Circular Arcs
• On Triangle Contact Graphs
• On the Density of Maximal 1-Planar Graphs
• Rectangular layouts and contact graphs
• On chromatic number of graphs and set-systems
• An inequality for the chromatic number of a graph
• k-Degenerate Graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• Contact graphs of line segments are NP-complete

This page was built for publication: Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs