Constrained Graph Layouts - Vertices on the Outer Face and on the Integer Grid

Constraining graph layouts - that is, restricting the placement of vertices and the routing of edges to obey certain constraints - is common practice in graph drawing.
In this book, we discuss algorithmic results on two different restriction types: placing vertices on the outer face and on the integer grid.
For the first type, we look into the outer k-planar and outer k-quasi-planar graphs, as well as giving a linear-time algorithm to recognize full and closed outer k-planar graphs Monadic Second-order Logic.
For the second type, we consider the problem of transferring a given planar drawing onto the integer grid while perserving the original drawings topology; we also generalize a variant of Cauchy's rigidity theorem for orthogonal polyhedra of genus 0 to those of arbitrary genus.

About the author

geboren 1987, M. Sc. (Informatik, Universität Würzburg)

Product details

• Authors: Andre Löffler
• Publisher: Würzburg University Press
• Languages: English
• Product format: Paperback / Softback
• Released: 14.01.2021
• EAN: 9783958261464
• ISBN: 978-3-95826-146-4
• No. of pages: 172
• Dimensions: 170 mm x 240 mm x 11 mm
• Weight: 339 g
• Subject: Natural sciences, medicine, IT, technology > Mathematics > Geometry