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…
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…
Weakly Leveled Planarity with Bounded Span
Michael Bekos, Giordano Da Lozzo, Fabrizio Frati +5
This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizonta…
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…