EPGrepresentations with Small GridSizeBiedl, Therese and Derka, Martin and Dujmović, Vida and Morin, Pat (2017) EPGrepresentations with Small GridSize. In: Graph Drawing and Network Visualization. GD 2017, September 2527 , pp. 184196(Official URL: https://doi.org/10.1007/9783319739151_16). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_16
AbstractIn an EPGrepresentation of a graph G, each vertex is represented by a path in the rectangular grid, and (v, w) is an edge in G if and only if the paths representing v an w share a gridedge. Requiring paths representing edges to be xmonotone or, even stronger, both x and ymonotone gives rise to three natural variants of EPGrepresentations, one where edges have no monotonicity requirements and two with the aforementioned monotonicity requirements. The focus of this paper is understanding how small a grid can be achieved for such EPGrepresentations with respect to various graph parameters. We show that there are medge graphs that require a grid of area Ω(m) in any variant of EPGrepresentations. Similarly there are pathwidthk graphs that require height Ω(k) and area Ω(kn) in any variant of EPGrepresentations. We prove a matching upper bound of O(kn) area for all pathwidthk graphs in the strongest model, the one where edges are required to be both x and ymonotone. Thus in this strongest model, the result implies, for example, O(n), O(nlogn) and O(n^3/2) area bounds for bounded pathwidth graphs, bounded treewidth graphs and all classes of graphs that exclude a fixed minor, respectively. For the model with no restrictions on the monotonicity of the edges, stronger results can be achieved for some graph classes, for example an O(n) area bound for bounded treewidth graphs and O(nlog^2 n) bound for graphs of bounded genus.
Actions (login required)
