7 papers
Beyond Degree Four: Near-Orthogonal Planar Drawings
Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo +2
Orthogonal planar drawings constitute a classical and mainstream research topic in graph drawing due to their clarity and wide applicability. In an orthogonal planar drawing of a g…
Towards the Recognition of Oriented Interval Graphs
Lukas P. Bachmann, JiÅà Fiala, Miriam Münch +3
Oriented interval graphs, a recent generalization of interval graphs introduced by Gutowski et al. [GD 2022], are intersection graphs of intervals, each of which is oriented either…
Upward Book Embeddings of Partitioned Digraphs
Giordano Da Lozzo, Fabrizio Frati, Ignaz Rutter
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in…
Circle graphs can be recognized in linear time
Christophe Paul, Ignaz Rutter
To date, the best circle graph recognition algorithm runs in almost linear time as it relies on a split decomposition algorithm that uses the union-find data-structure. We show tha…
The Price of Upwardness
Patrizio Angelini, Therese Biedl, Markus Chimani +8
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyon…
Simple Realizability of Abstract Topological Graphs
Giordano Da Lozzo, Walter Didimo, Fabrizio Montecchiani +3
An abstract topological graph (AT-graph) is a pair , where is a graph and is a set of pairs of edges of . A re…