Treetopes and their graphs

DOI10.1007/S00454-020-00177-0MaRDI QIDQ2197683zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 1 September 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.03152

zbMATH Keywords

treepolytopeskeletonHalin graphclustered planarity

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Three-dimensional polytopes (52B10) Graph representations (geometric and intersection representations, etc.) (05C62) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Recommendations

• Treetopes and their Graphs
• Zur Struktur der (\({\mathfrak P}^ 3\))-realisierbaren Graphen. (On the structure of (\({\mathfrak P}^ 3\)-realizable graphs))
• Tree polytope on 2-trees
• Einfache, konvexe Polytope und ihre Graphen
• Simple polytopes without small separators. II: Thurston's bound

Cites work

• scientific article; zbMATH DE number 3937204 (Why is no real title available?)
• scientific article; zbMATH DE number 3536105 (Why is no real title available?)
• scientific article; zbMATH DE number 2068109 (Why is no real title available?)
• scientific article; zbMATH DE number 3346402 (Why is no real title available?)
• A 3-approximation for the pathwidth of Halin graphs
• A linear algorithm for embedding planar graphs using PQ-trees
• A new planarity test
• A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
• Approximation algorithms for polynomial-expansion and low-density graphs
• Atomic embeddability, clustered planarity, and thickenability
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• Complexity of some geometric and topological problems
• Convex Polytopes
• Efficient Planarity Testing
• Finding a simple polytope from its graph in polynomial time
• Finding small simple cycle separators for 2-connected planar graphs
• Halin graphs and the travelling salesman problem
• Longest Simple Paths in Polyhedral Graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• On the graph structure of convex polyhedra in \(n\)-space
• On the number of certain types of polyhedra
• Planar Separators
• Planarity Allowing Few Error Vertices in Linear Time
• Planarity for clustered graphs
• Preassigning the shape of a face
• Realization spaces of 4-polytopes are universal
• Recognizing Cartesian products in linear time
• Simple recognition of Halin graphs and their generalizations
• Sparsity. Graphs, structures, and algorithms
• Strongly sublinear separators and polynomial expansion
• TRÉMAUX TREES AND PLANARITY
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(6)

• scientific article; zbMATH DE number 6479553 (Why is no real title available?)
• Trees, ladders and graphs
• scientific article; zbMATH DE number 5642074 (Why is no real title available?)
• scientific article; zbMATH DE number 2107061 (Why is no real title available?)
• Acyclic, connected and tree sets
• The topological trees with extreme Matula numbers

This page was built for publication: Treetopes and their graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197683)