Treewidth, Circle Graphs, and Circular Drawings
From MaRDI portal
Publication:6195956
DOI10.1137/22m1542854arXiv2212.11436MaRDI QIDQ6195956
Freddie Illingworth, Bojan Mohar, Robert Hickingbotham, David R. Wood
Publication date: 14 March 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2212.11436
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. III. Planar tree-width
- A characterization of circle graphs
- On tree-partition-width
- On the chromatic number of multiple interval graphs and overlap graphs
- Isotropic systems
- Graphic presentations of isotropic systems
- Embedding planar graphs in four pages
- On the thickness of graphs of given degree
- Graphs drawn with few crossings per edge
- A partial k-arboretum of graphs with bounded treewidth
- Covering and coloring polygon-circle graphs
- The thickness of graphs: A survey
- A successful concept for measuring non-planarity of graphs: The crossing number.
- Diameter and treewidth in minor-closed graph families
- Gap-planar graphs
- Which crossing number is it anyway?
- The graph crossing number and its variants: a survey
- On the tree-width of even-hole-free graphs
- The grid theorem for vertex-minors
- Tree-width dichotomy
- Stack-number is not bounded by queue-number
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- Planar graphs that need four pages
- Graph treewidth and geometric thickness parameters
- Planar decompositions and the crossing number of graphs with an excluded minor
- Rank-width: algorithmic and structural results
- Layered separators in minor-closed graph classes with applications
- The book thickness of 1-planar graphs is constant
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Algorithms for graphs embeddable with few crossings per edge
- Approximating clique-width and branch-width
- Homomorphiesätze für Graphen
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Rank-width and vertex-minors
- Grid induced minor theorem for graphs of small degree
- Parameters Tied to Treewidth
- Bounds for Convex Crossing Numbers
- Improved Circular Layouts
- Crossing Numbers of Graphs
- Some results on tree decomposition of graphs
- TREEWIDTH OF CIRCLE GRAPHS
- Circle graphs are quadratically χ‐bounded
- Improved bounds for colouring circle graphs
- Tree densities in sparse graph classes
- A survey of χ‐boundedness
- Four pages are indeed necessary for planar graphs
- Minimizing crossings in constrained two-sided circular graph layouts.
- Structure of Graphs with Locally Restricted Crossings
- The crossing number of K5,n
- Embedding planar graphs at fixed vertex locations
- (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
- (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
- Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
- Induced subgraphs and path decompositions
- Graph product structure for non-minor-closed classes
