Showing 2025Show all
3 papers · 1 filter
cs.DS2025
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…
cs.CG2025
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…
cs.DS2025
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…