EPG-representations with Small Grid-Size

Biedl, Therese and Derka, Martin and Dujmović, Vida and Morin, Pat (2017) EPG-representations with Small Grid-Size. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 184-196(Official URL: https://doi.org/10.1007/978-3-319-73915-1_16).

Full text not available from this repository.


In an EPG-representation 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 grid-edge. Requiring paths representing edges to be x-monotone or, even stronger, both x- and y-monotone gives rise to three natural variants of EPG-representations, 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 EPG-representations with respect to various graph parameters. We show that there are m-edge graphs that require a grid of area Ω(m) in any variant of EPG-representations. Similarly there are pathwidth-k graphs that require height Ω(k) and area Ω(kn) in any variant of EPG-representations. We prove a matching upper bound of O(kn) area for all pathwidth-k graphs in the strongest model, the one where edges are required to be both x- and y-monotone. 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
P Styles > P.600 Poly-line > P.600.700 Orthogonal
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1603

Actions (login required)

View Item View Item