4-Connected Triangulations on Few Lines

DOI10.1007/978-3-030-35802-0_30arXiv1908.04524MaRDI QIDQ6323587FDOQ6323587

Authors: Stefan Felsner 

Publication date: 13 August 2019

Abstract: We show that 4-connected plane triangulations can be redrawn such that edges are represented by straight segments and the vertices are covered by a set of at most $sqrt2n$ lines each of them horizontal or vertical. The same holds for all subgraphs of such triangulations. The proof is based on a corresponding result for diagrams of planar lattices which makes use of orthogonal chain and antichain families.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: 4-Connected Triangulations on Few Lines

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