EPG-representations with Small Grid-Size

DOI10.1007/978-3-319-73915-1_16MaRDI QIDQ4625111zbMATH OpenOpenAlexFDO

Authors Martin Derka, Vida Dujmović, Pat Morin, Therese Biedl

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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 $Omega(m)$ in any variant of EPG-representations. Similarly there are pathwidth-$k$ graphs that require height $Omega(k)$ and area $Omega(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(nlo{g}^{2}n)$ bound for graphs of bounded genus.

Recommendations

• EpGs with minimal \(\mu\). II
• Optimal grid representations
• Segment representations with small resolution
• Compact grid representation of graphs
• Small-size -nets for axis-parallel rectangles and boxes
• Small-size ε-nets for axis-parallel rectangles and boxes
• Compact Multigrid
• Compressing grids into small hypercubes
• Efficient embeddings of grids into grids
• Embedding grids into grids: Techniques for large compression ratios

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic graph theory and perfect graphs
• Constant-degree graph expansions that preserve treewidth
• Edge intersection graphs of systems of paths on a grid with a bounded number of bends
• Edge-intersection graphs of grid paths: the bend-number
• Elliptic curve cryptography on the WISP UHF RFID tag
• Energy-efficient elliptic curve cryptography for MSP430-based wireless sensor nodes
• Four (mathbbQ) on embedded devices with strong countermeasures against side-channel attacks
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers
• High-speed high-security signatures
• scientific article; zbMATH DE number 4191111 (Why is no real title available?)
• scientific article; zbMATH DE number 2085203 (Why is no real title available?)
• scientific article; zbMATH DE number 1878328 (Why is no real title available?)
• scientific article; zbMATH DE number 2114384 (Why is no real title available?)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Mote-ECC: energy-scalable elliptic curve cryptography for wireless sensor networks
• Optimal security proofs for signatures from identification schemes
• Public Key Cryptography - PKC 2006
• Speeding the Pollard and Elliptic Curve Methods of Factorization
• Taming the many EdDSAs
• Treewidth of graphs with balanced separations
• Twisted Edwards Curves
• Twisted Edwards Curves Revisited
• Validation of Elliptic Curve Public Keys
• VPG and EPG bend-numbers of Halin graphs

Cited in

(3)

• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings
• Compact grid representation of graphs

This page was built for publication: EPG-representations with Small Grid-Size

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