Lower Bounds, Graph Embeddings, Combinatorial Preconditioners, Gary L. Miller, Peter C. Richter
Given a general graph G, a fundamental problem is to find a spanning tree H that best approximates G by some measure. Often this measure is some combination of the congestion and dilation of an...
On Self Duality of Pathwidth in Polyhedral Graph (2006)
Graph Embeddings, Fedor V. Fomin, Dimitrios M. Thilikos
Let G be a 3-connected planar graph and G ∗ be its dual. We show that the pathwidth of G ∗ is at most 6 times the pathwidth of G. We prove this result by relating the pathwidth of a graph with...
Centrally-symmetric Tight Surfaces and Graph Embeddings (1996)
Graph Embeddings, Wolfgang Kühnel
. We prove a sharp upper bound for the substantial codimension of a centrally-symmetric tight polyhedral surface in Euclidean space. This is related to embeddings of the edge graph of the...