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 which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph G = (V, ⋃^k_{i=1} E_i), that is, a digraph whose edge set is partitioned into k subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput. 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for k = 1 and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for k ≥ 3. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case k = 2. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when k = 2, thus closing the complexity gap for the problem. Second, we show that, for an n-vertex partitioned digraph with a prescribed planar embedding, the existence of an upward book embedding that respects the given planar embedding can be tested in O(n log³ n) time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial 2-trees.

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 left or right. Such a representation defines a mixed intersection graph: overlapping intervals with the same orientation define a (directed) arc; nested intervals (irrespective of the orientations of the intervals) and overlapping intervals of opposite orientations define an (undirected) edge. An oriented interval representation of a mixed graph G can be described combinatorially by the combination of (i) an orientation φ : V(G) → {-1,1} of all intervals, (ii) a clique ordering σ, and (iii) a set E_cont ⊆ E(G) of containment edges, which are represented by nested intervals. The non-trivial dependencies between these three ingredients make the recognition of oriented interval graphs a challenging problem. In this paper, we take steps towards a general recognition algorithm by studying how orientation, clique ordering, and containment edges influence and restrict each other. We characterize the orientations that are consistent with a given set of containment edges as well as the clique orderings that are consistent with a given orientation. Based on these characterizations, we give linear-time algorithms for two constrained versions of the recognition problem where, in addition to the mixed input graph G, either the set of containment edges E_cont or the orientation φ is prescribed. This improves a quadratic-time algorithm of Gutowski et al. for the case that all vertices have the same orientation; an assumption that determines both the orientation and the containment edges. In particular, this also solves the recognition problem for oriented proper (or unit) interval graphs.

To date, the best circle graph recognition algorithm, due to Gioan et al. [E. Gioan et al., 2014] runs in almost linear time as it relies on a split decomposition algorithm [E. Gioan et al., 2014] that uses the union-find data-structure [B.A. Galler and M.J. Fischer, 1964; R. Tarjan, 1975]. We show that in the case of circle graphs, the PC-tree data-structure [W. K. Shih and W. L. Hsu, 1999] allows one to avoid the union-find data-structure to compute the split decomposition in linear time. As a consequence, we obtain the first linear-time recognition algorithm for circle graphs.

We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span.

Abstract Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on one of k given horizontal lines and edges are drawn as y -monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimisation (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of the vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We analyse the performance of simple evolutionary algorithms for OBCM and compare different operators for permutations: exchanging two elements, swapping adjacent elements and jumping an element to a new position. We show that on instances that can be drawn crossing-free, OBCM corresponds to a generalised sorting problem. We provide novel and tight lower bounds of $$\Omega (n^2 \log n)$$ for sorting with exchanges and jumps, respectively. This solves a long-standing open problem by Scharnow, Tinnefeld, and Wegener (J. Math. Model. Algorithm 3(4):349–366, 2005). For the simplest and cheapest mutation operator, swap (swapping adjacent elements), we give a tight runtime bound of $$\Theta (n^2)$$ via a parallel BubbleSort algorithm and a delay sequence argument. This proves that the simplest and cheapest mutation operator is also the fastest for sorting and solving planar OBCM instances.

An outer-string representation of a graph is an intersection representation in which each vertex is represented by a curve that is contained in the unit disk and has at least one endpoint on the boundary of the unit disk. In an outer-1-string representation the curves representing any two vertices are in addition allowed to intersect at most once. In this paper, we consider the following constrained version: Given a graph G plus a cyclic order v1, . . . , vn of the vertices in G, test whether G has an outer-string or an outer-1-string representation in which the curves representing v1, . . . , vn intersect the boundary of the unit disk in this order. We first show that a graph has an outer-string representation for all possible cyclic orders of the vertices if and only if the graph is the complement of a chordal graph. Then we turn towards the situation where one particular cyclic order of the vertices is fixed. We characterize the chordal graphs admitting a constrained outer-string representation and the trees and cycles admitting a constrained outer-1-string representation. The characterizations yield polynomial-time recognition and construction algorithms; in the case of outer-1-string representations the run time is linear. We also show how to decide in polynomial time whether an arbitrary graph admits a constrained L-shaped outer-1-string representation. In an L-shaped representation the curves are 1-bend orthogonal polylines anchored on a horizontal line, and they are contained in the half-plane below that line. However, not even all paths with a constrained outer-1-string representation admit one with L-shapes. We show that 2-bend orthogonal polylines are sufficient for trees and cycles with a constrained outer-1-string representation.

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 horizontal segment or a strictly y -monotone curve. A graph is s -span weakly leveled planar if it admits such a drawing where the edges have span at most s ; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s -span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n )-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds.

We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs [Kaufmann et al., 2024] can be used to count the crossings in terms of the number n of vertices. As a main result, we show that every 3-plane drawing has at most 5.5(n-2) crossings, which is tight. In particular, it follows that every 3-planar graph on n vertices has crossing number at most 5.5n, which improves upon a recent bound [Bekos et al., 2024] of 6.6n. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most 5.5(n-2) edges.

Very recently, Chambers, Fasy, Hosseini Sereshgi and Löffler [Erin W. Chambers et al., 2025] showed that every Reeb caterpillar admits a crossing-free drawing. It turns out that this does not hold for Reeb lobsters but we show that these graphs admit drawings with at most one crossing per edge.

Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on a horizontal line and edges are drawn as y-monotone curves. We consider a fundamental problem from this domain, the One-Sided Bipartite Crossing Minimisation (OBCM) problem. Given a bipartite graph with two layers and a fixed horizontal order of vertices on the first layer, the objective is to order the vertices on the second layer to minimise the number of edge crossings.

A decision tree recursively splits a feature space R d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space R d , which contains n training examples. We show that it can be solved in O ( n 2 d + 1 ) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f ( d ) ⋅ n o ( d / log ⁡ d ) running time. The problem is solvable in ( d R ) O ( d R ) ⋅ n 1 + o ( 1 ) time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

Abstract In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs—the simultaneous version of arguably one of the most well-studied graph classes—is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more ‘rigid’ and therefore have less freedom in their representation. We show they can be recognized in time $$\mathcal {O}(|V|\cdot |E|)$$ O ( | V | · | E | ) for any number of simultaneous graphs in the sunflower case where $$G=(V,E)$$ G = ( V , E ) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

Let G = ( V , E ) be a directed graph and ℓ : V → [ k ] : = { 1 , 2 , … , k } a level assignment such that ℓ ( u ) < ℓ ( v ) for all directed edges ( u , v ) ∈ E . A level-planar drawing of G maps each vertex v to a unique point on the horizontal line ℓ with y -coordinate ℓ ( v ) and each directed edge to a y -monotone Jordan arc between its endpoints such that no two arcs cross in their interior. In the problem Constrained Level Planarity ( CLP for short), we are further given a partial ordering ◁ i of V i : = ℓ − 1 ( i ) for each i ∈ [ k ] , and we seek a level-planar drawing where the linear order ≺ i of the vertices on ℓ i is a linear extension of ◁ i . A special case of this is the problem Partial Level Planarity ( PLP for short), where we are asked to extend a given level-planar drawing H of a subgraph H of G to a complete drawing G of G without modifying the given drawing, i.e., the restriction of G to H must coincide with H . We give a simple polynomial-time algorithm with running time O ( n 5 ) for CLP of single-source graphs that is based on a simplified version of an existing level-planarity testing algorithm for single-source graphs. We introduce a modified type of PQ-tree data structure that is capable of efficiently handling the arising constraints to improve the running time to O ( n + k s ) , where s denotes the size of the constraints. We complement this result by showing that PLP is NP -complete even in very restricted cases. In particular, PLP remains NP -complete even when G has a constant number of levels, and when G is a subdivision of a triconnected planar graph with bounded degree.

In the constrained planarity setting, we ask whether a graph admits a planar drawing that additionally satisfies a given set of constraints. These constraints are often derived from very natural problems; prominent examples are Level planarity, where vertices have to lie on given horizontal lines indicating a hierarchy, and clustered planarity, where we additionally draw the boundaries of clusters which recursively group the vertices in a crossing-free manner. Despite receiving significant amount of attention and substantial theoretical progress on these problems, only very few of the found solutions have been put into practice and evaluated experimentally.

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 beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-$k$-planarity is NP-complete already for $k=1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.

Evolutionary algorithms (EAs) are universal solvers inspired by principles of natural evolution. In many applications, EAs produce astonishingly good solutions. To complement recent theoretical advances in the analysis of EAs on graph drawing [Baumann et al., 2024], we contribute a fundamental empirical study. We consider the so-called One-Sided Bipartite Crossing Minimisation (OBCM): given two layers of a bipartite graph and a fixed horizontal order of vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We empirically analyse the performance of simple EAs for OBCM and compare different mutation operators on the underlying permutation ordering problem: exchanging two elements (exchange), swapping adjacent elements (swap) and jumping an element to a new position (jump). EAs using jumps easily outperform all deterministic algorithms in terms of solution quality after a reasonable number of generations. We also design variations of the best-performing EAs to reduce the execution time for each generation. The improved EAs can obtain the same solution quality as before and run up to 100 times faster.

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 horizontal segment or a strictly $y$-monotone curve. A graph is $s$-span weakly leveled planar if it admits such a drawing where the edges have span at most $s$; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing $s$-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter $s$ and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of $2$-outerplanar graphs generalizing Halin graphs, are $Θ(\log n)$-span weakly leveled planar and $4$-span weakly leveled planar when $3$-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

We consider three simple quadratic time algorithms for the problem Level Planarity and give a level-planar instance that they either falsely report as negative or for which they output a drawing that is not level planar.

We introduce the $k$-Plane Insertion into Plane drawing ($k$-PIP) problem: given a plane drawing of a planar graph $G$ and a set $F$ of edges, insert the edges in $F$ into the drawing such that the resulting drawing is $k$-plane. In this paper, we show that the problem is NP-complete for every $k\ge 1$, even when $G$ is biconnected and the set $F$ of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that $k=1$ and $G$ is a triangulation.

A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to one out of six possible crossing types, where a type characterizes the subgraph induced by the four vertices of the crossing edges. Each of the 63 possible nonempty subsets 𝒮 of crossing types gives a recognition problem: does a given graph admit an 𝒮-restricted drawing, that is, a 1-planar drawing where the crossing type of each crossing is in 𝒮? We show that there is a set 𝒮_bad with three crossing types and the following properties: - If 𝒮 contains no crossing type from 𝒮_bad, then the recognition of graphs that admit an 𝒮-restricted drawing is fixed-parameter tractable with respect to the treewidth of the input graph. - If 𝒮 contains any crossing type from 𝒮_bad, then it is NP-hard to decide whether a graph has an 𝒮-restricted drawing, even when considering graphs of constant pathwidth. We also extend this characterization of crossing types to 1-planar straight-line drawings and show the same complexity behaviour parameterized by treewidth.

Graph Drawing aims to make graphs visually comprehensible while faithfully representing their structure. In layered drawings, each vertex is drawn on a horizontal line and edges are drawn as y-monotone curves. A key ingredient for constructing such drawings is the One-Sided Bipartite Crossing Minimisation (OBCM) problem: given two layers of a bipartite graph and a fixed horizontal order of the vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings.

An abstract topological graph (AT-graph) is a pair $A=(G,\mathcal{X})$, where $G=(V,E)$ is a graph and $\mathcal{X} \subseteq {E \choose 2}$ is a set of pairs of edges of $G$. A realization of $A$ is a drawing $Γ_A$ of $G$ in the plane such that any two edges $e_1,e_2$ of $G$ cross in $Γ_A$ if and only if $(e_1,e_2) \in \mathcal{X}$; $Γ_A$ is simple if any two edges intersect at most once (either at a common endpoint or at a proper crossing). The AT-graph Realizability (ATR) problem asks whether an input AT-graph admits a realization. The version of this problem that requires a simple realization is called Simple AT-graph Realizability (SATR). It is a classical result that both ATR and SATR are NP-complete. In this paper, we study the SATR problem from a new structural perspective. More precisely, we consider the size $\mathrmλ(A)$ of the largest connected component of the crossing graph of any realization of $A$, i.e., the graph ${\cal C}(A) = (E, \mathcal{X})$. This parameter represents a natural way to measure the level of interplay among edge crossings. First, we prove that SATR is NP-complete when $\mathrmλ(A) \geq 6$. On the positive side, we give an optimal linear-time algorithm that solves SATR when $\mathrmλ(A) \leq 3$ and returns a simple realization if one exists. Our algorithm is based on several ingredients, in particular the reduction to a new embedding problem subject to constraints that require certain pairs of edges to alternate (in the rotation system), and a sequence of transformations that exploit the interplay between alternation constraints and the SPQR-tree and PQ-tree data structures to eventually arrive at a simpler embedding problem that can be solved with standard techniques.

Abstract The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph $$H \subseteq G$$ H ⊆ G and a representation $$\mathcal R'$$ R ′ of H. The question is whether G admits a representation $$\mathcal R$$ R whose restriction to H is $$\mathcal R'$$ R ′ . We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in $$O((n + m) \alpha (n + m))$$ O ( ( n + m ) α ( n + m ) ) time, thereby improving over an $$O(n^3)$$ O ( n 3 ) -time algorithm by Chaplick et al. (J Graph Theory 91(4), 365–394, 2019). The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.

Abstract A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.

Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1. The problem Pathwidth-One Vertex Explosion (POVE) asks whether such a graph can be obtained using at most 𝑘 vertex explosions, where a vertex explosion replaces a vertex 𝑣 by deg(𝑣) degree-1 vertices, each incident to exactly one edge that was originally incident to 𝑣. For POVE, we give an FPT algorithm with running time 𝑂(4𝑘 ⋅ 𝑚) and an 𝑂(𝑘2) kernel, thereby improving over the 𝑂(𝑘6) kernel by Ahmed et al. [2] in a more general setting. Similarly, a vertex split replaces a vertex 𝑣 by two distinct vertices 𝑣1 and 𝑣2 and distributes the edges originally incident to 𝑣 arbitrarily to 𝑣1 and 𝑣2. Analogously to POVE, we define the problem variant Pathwidth-One Vertex Splitting (POVS) that uses the split operation instead of vertex explosions. Here we obtain a linear kernel and an algorithm with running time 𝑂((6𝑘 + 12)𝑘 ⋅ 𝑚). This answers an open question by Ahmed et al. [2]. Finally, we consider the problem Π-VertexSplitting (Π-VS), which generalizes the problem POVS and asks whether a given graph can be turned into a graph of a specific graph class Π using at most 𝑘 vertex splits. For graph classes Π that can be dfined in monadic second-order graph logic (MSO2), we show that the problem Π-VS can be expressed as an MSO2 formula, resulting in an FPT algorithm for Π-VS parameterized by 𝑘 if Π additionally has bounded treewidth. We obtain the same result for the problem variant using vertex explosions. [2] R. Ahmed, S.G. Kobourov, M. Kryven, An FPT algorithm for bipartite vertex splitting, in: P. Angelini, R. von Hanxleden (Eds.), Graph Drawing and Network Visualization -30th International Symposium, GD 2022, in: Lecture Notes in Computer Science, vol.13764, Springer, 2022, pp.261--268.

A decision tree recursively splits a feature space \mathbb{R}^d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space \mathbb{R}^d, which contains n training examples. We show that it can be solved in O(n^(2d + 1)) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d) * n^o(d / log d) running time. The problem is solvable in (dR)^O(dR) * n^(1+o(1)) time, if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G=(V,E) into a planar straight-line circular drawing of G by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is obvious that such a crossing-free circular drawing always exists and we define the circular shifting number shift∘(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift∘(δG)≤K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift∘(δG)≤n−⌊n−2⌋−2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all of the crossings. For this problem, we provide a tight upper bound shift∘(δG)≤⌊n2⌋−1 and present an O(n2)-time algorithm to compute the circular shifting number of almost-planar drawings.

Abstract Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. In this work, we generalize this idea to ortho-radial representations of ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. Unlike the orthogonal case, there exist ortho-radial representations that do not admit a corresponding drawing, for example so-called strictly monotone cycles. An ortho-radial representation is called valid if it does not contain a strictly monotone cycle. Our first main result is that an ortho-radial representation admits a corresponding drawing if and only if it is valid. Previously such a characterization was only known for ortho-radial drawings of paths, cycles, and theta graphs (Hasheminezhad et al. in Australas J Combin 44:171–182, 2009), and in the special case of rectangular drawings of cubic graphs (Hasheminezhad et al. in Comput Geom 43(9):767–780, 2010), where the contour of each face is required to be a combinatorial rectangle. Additionally, we give a quadratic-time algorithm that tests for a given ortho-radial representation whether it is valid, and we show how to draw a valid ortho-radial representation in the same running time. Altogether, this reduces the problem of computing a minimum-bend ortho-radial drawing to the task of computing a valid ortho-radial representation with the minimum number of bends, and hence establishes an ortho-radial analogue of the topology-shape-metrics framework for planar orthogonal drawings by Tamassia (SIAM J Comput 16(3):421–444, 1987).

We study the complexity of testing whether a biconnected graph G=(V,E) is planar with the constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are described by associating every vertex v of G with a set D(v) of FPQ-trees. Let tw be the treewidth of G and let Dmax be the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw+Dmax, paraNP-hard when parameterized by Dmax, and W[1]-hard when parameterized by tw. We also consider NodeTrix planar representations of clustered graphs, where clusters are adjacency matrices and inter-cluster edges are non-intersecting simple curves. We prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of clusters plus the treewidth of the graph obtained by collapsing clusters to single vertices, provided that this graph is biconnected.

We introduce the problem S ynchronized P lanarity . Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. S ynchronized P lanarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that S ynchronized P lanarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of S ynchronized P lanarity . In particular, this lets us solve C lustered P lanarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O ( n 8 ).

Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)α(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $α$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.

We study a fundamental question from graph drawing: given a pair $(G,C)$ of a graph $G$ and a cycle $C$ in $G$ together with a simple polygon $P$, is there a straight-line drawing of $G$ inside $P$ which maps $C$ to $P$? We say that such a drawing of $(G,C)$ respects $P$. We fully characterize those instances $(G,C)$ which are polygon-universal, that is, they have a drawing that respects $P$ for any simple (not necessarily convex) polygon $P$. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance $(G,C)$ is planar, that is, if there exists a planar drawing of $G$ with $C$ on the outer face, we show that the same conditions guarantee for every simple polygon $P$ the existence of a planar drawing of $(G,C)$ that respects $P$. If $(G,C)$ is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon $P$.

We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent. We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerful modeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O(n⁸).

We study the planar orthogonal drawing style within the framework of partial representation extension. Let $$(G,H,\varGamma _H)$$ be a partial orthogonal drawing, i.e., G is a graph, $$H\subseteq G$$ is a subgraph and $$\varGamma _H$$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing $$\varGamma _G$$ of G that extends $$\varGamma _H$$ can be tested in linear time. If such a drawing exists, then there also is one that uses O(|V(H)|) bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge.

An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given set of constraints. We develop an SPQR-tree-like data structure that represents all level-planar embeddings of a biconnected level graph with a single source, called the LP-tree, and give a simple algorithm to compute it in linear time. Moreover, we show that LP-trees can be used to adapt three constrained planarity algorithms to the level-planar case by using them as a drop-in replacement for SPQR-trees.

Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. Barth et al. [2017] have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation. In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation. Using further structural insights we speed up the drawing algorithm to quadratic running time.

We consider the minimization of edge-crossings in geometric drawings of graphs $G=(V, E)$, i.e., in drawings where each edge is depicted as a line segment. The respective decision problem is NP-hard [Bienstock, '91]. In contrast to theory and the topological setting, the geometric setting did not receive a lot of attention in practice. Prior work [Radermacher et al., ALENEX'18] is limited to the crossing-minimization in geometric graphs with less than $200$ edges. The described heuristics base on the primitive operation of moving a single vertex $v$ to its crossing-minimal position, i.e., the position in $\mathbb{R}^2$ that minimizes the number of crossings on edges incident to $v$. In this paper, we introduce a technique to speed-up the computation by a factor of $20$. This is necessary but not sufficient to cope with graphs with a few thousand edges. In order to handle larger graphs, we drop the condition that each vertex $v$ has to be moved to its crossing-minimal position and compute a position that is only optimal with respect to a small random subset of the edges. In our theoretical contribution, we consider drawings that contain for each edge $uv \in E$ and each position $p \in \mathbb{R}^2$ for $v$ $o(|E|)$ crossings. In this case, we prove that with a random subset of the edges of size $Θ(k \log k)$ the co-crossing number of a degree-$k$ vertex $v$, i.e., the number of edge pairs $uv \in E, e \in E$ that do not cross, can be approximated by an arbitrary but fixed factor $δ$ with high probability. In our experimental evaluation, we show that the randomized approach reduces the number of crossings in graphs with up to $13\,000$ edges considerably. The evaluation suggests that depending on the degree-distribution different strategies result in the fewest number of crossings.

In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs - the simultaneous version of arguably one of the most well-studied graph classes - is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more "rigid" and therefore have less freedom in their representation. We show they can be recognized in time O(|V|*|E|) for any number of simultaneous graphs in the sunflower case where G=(V,E) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

Mutual information is a measure for both linear and non-linear associations between variables. There exist several estimators of mutual information for static data. In the dynamic case, one needs to apply these estimators to samples of points from data streams. The sampling should be such that more detailed information on the recent past is available. We formulate a list of natural requirements an estimator of mutual information on data streams should fulfill, and we propose two approaches which do meet all of them. Finally, we compare our algorithms to an existing method both theoretically and experimentally. Our findings include that our approaches are faster and have lower bias and better memory complexity.

In this paper we consider the rectilinear crossing minimization problem, i.e., we seek a straight-line drawing Г of a graph G = (V, E) with a small number of edge crossings. Crossing minimization is an active field of research [1,9]. While there is a lot of work on heuristics for topological drawings, these techniques are typically not transferable to the rectilinear (i.e., straight-line) setting. We introduce and evaluate three heuristics for rectilinear crossing minimization. The approaches are based on the primitive operation of moving a single vertex to its crossing-minimal position in the current drawing Γ, for which we give an O ((kn + m)2 log (kn + m))-time algorithm, where k is the degree of the vertex and n and m are the numbers of vertices and edges of the graph, respectively. In an experimental evaluation, we demonstrate that our algorithms compute straight-line drawings with fewer crossings than energy-based algorithms implemented in the Open Graph Drawing Framework [10] on a varied set of benchmark instances. All experiments are evaluated with a statistical significance level of α = 0.05.

This abstract describes how tools from network analysis and visualization can successfully support the study of philosophical questions in social epistemology. We introduce a particular network structure, namely the (m, k)-observer. We argue for its epistemic value and show that such observers are extremely rare in social media discussions of controversial topics. Our specific use case concerns a discussion of vaccine safety on Twitter.

Mutual Information (MI) is an established measure for the dependence of two variables and is often used as a generalization of correlation measures. Existing methods to estimate MI focus on static data. However, dynamic data is ubiquitous as well, and MI estimates on it are useful for stream mining and advanced monitoring tasks. In dynamic data, small changes (e.g., insertion or deletion of a value) may often invalidate the previous estimate. In this article, we study how to efficiently adjust an existing MI estimate when such a change occurs. As a first step, we focus on the well-known nearest-neighbor based estimators for static data and derive a tight lower bound for their computational complexity, which is unknown so far. We then propose two dynamic data structures that can update existing estimates asymptotically faster than any approach that computes the estimates independently, i.e., from scratch. Next, we infer a lower bound for the computational complexity of such updates, irrespective of the data structure and the algorithm, and present an algorithm that is only a logarithmic factor slower than this bound. In absolute numbers, these solutions offer fast and accurate estimates of MI on dynamic data as well.

Consider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This problem, called Max Facial C-Cycles, was first studied by Mutzel and Weiskircher [IPCO '99, http://dx.doi.org/10.1007/3-540-48777-8_27) and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002, http://dx.doi.org/10.1016/S0167-6377(02)00119-0]. We establish a tight border of tractability for Max Facial C-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial C-Cycles. Namely, we give a 2-approximation for series-parallel graphs and a (4+epsilon)-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems.

Given a planar graph G and a partition of the neighbors of each vertex v in four sets v ↗ , v ↖ , v ↙ , and v ↘ , the problem W indrose P lanarity asks to decide whether G admits a windrose-planar drawing , that is, a planar drawing in which (i) each neighbor u ∈ v ↗ v is above and to the right of v , (ii) each neighbor u ∈ v ↖ is above and to the left of v , (iii) each neighbor u ∈ v ↙ is below and to the left of v , (iv) each neighbor u ∈ v ↘ is below and to the right of v , and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow us to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP -hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with n vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most 2 n −5 bends in total, which lies on the 3 n × 3 n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

The usefulness of technical drawings as well as scientific illustrations such as medical drawings of human anatomy essentially depends on the placement of labels that describe all relevant parts of the figure. In order to not spoil or clutter the figure with text, the labels are often placed around the figure and are associated by thin connecting lines to their features, respectively. This labeling technique is known as external label placement. In this paper we introduce a flexible and general approach for external label placement assuming a contour of the figure prescribing the possible positions of the labels. While much research on external label placement aims for fast labeling procedures for interactive systems, we focus on highest-quality illustrations. Based on interviews with domain experts and a semi-automatic analysis of 202 handmade anatomical drawings, we identify a set of 18 layout quality criteria, naturally not all of equal importance. We design a new geometric label placement algorithm that is based only on the most important criteria. Yet, other criteria can flexibly be included in the algorithm, either as hard constraints not to be violated or as soft constraints whose violation is penalized by a general cost function. We formally prove that our approach yields labelings that satisfy all hard constraints and have minimum overall cost. Introducing several speedup techniques, we further demonstrate how to deploy our approach in practice. In an experimental evaluation on real-world anatomical drawings we show that the resulting labelings are of high quality and can be produced in adequate time.

Ortho-Radial drawings are a generalization of orthogonal drawings to grids that are formed by concentric circles and straight-line spokes emanating from the circles' center. Such drawings have applications in schematic graph layouts, e.g., for metro maps and destination maps. A plane graph is a planar graph with a fixed planar embedding. We give a combinatorial characterization of the plane graphs that admit a planar ortho-radial drawing without bends. Previously, such a characterization was only known for paths, cycles, and theta graphs, and in the special case of rectangular drawings for cubic graphs, where the contour of each face is required to be a rectangle. The characterization is expressed in terms of an ortho-radial representation that, similar to Tamassia's orthogonal representations for orthogonal drawings describes such a drawing combinatorially in terms of angles around vertices and bends on the edges. In this sense our characterization can be seen as a first step towards generalizing the Topology-Shape-Metrics framework of Tamassia to ortho-radial drawings.

Let G = (V, E) be a directed graph and ℓ: V → [k] := {1,…, k} a level assignment such that ℓ(u) < ℓ(v) for all directed edges (u, v) ∊ E. A level planar drawing of G is a drawing of G where each vertex v is mapped to a unique point on the horizontal line íj with y-coordinate í(v), and each edge is drawn as a y-monotone curve between its endpoints such that no two curves cross in their interior. In the problem Constrained Level Planarity (CLP for short), we are further given a partial ordering of Vi := ℓ−1(i) for i ∊ [k], and we seek a level planar drawing where the order of the vertices on ℓi is a linear extension of A special case of this is the problem Partial Level Planarity (PLP for short), where we are asked to extend a given level-planar drawing H of a subgraph H ⊆ G to a complete drawing G of G without modifying the given drawing, i.e., the restriction of G to H must coincide with H. We give a simple polynomial-time algorithm with running time O(n5) for CLP of single-source graphs that is based on a simplified version of an existing level- planarity testing algorithm for single-source graphs. We introduce a modified type of PQ-tree data structure that is capable of efficiently handling the arising constraints to improve the running time to O(n + kℓ), where ℓ is the size of the constraints. We complement this result by showing that PLP is NP-complete even in very restricted cases. In particular, PLP remains NP- complete even when G is a subdivision of a triconnected planar graph with bounded degree.

Isocontours in road networks represent the area that is reachable from a source within a given resource limit. We study the problem of computing accurate isocontours in realistic, large-scale networks. We propose isocontours represented by polygons with minimum number of segments that separate reachable and unreachable components of the network. Since the resulting problem is not known to be solvable in polynomial time, we introduce several heuristics that run in (almost) linear time and are simple enough to be implemented in practice. A key ingredient is a new practical linear-time algorithm for minimum-link paths in simple polygons. Experiments in a challenging realistic setting show excellent performance of our algorithms in practice, computing near-optimal solutions in a few milliseconds on average, even for long ranges.

Given a planar graph G(V, E) and a partition of the neighbors of each vertex v ∊ V in four sets , and , the problem Windrose Planarity asks to decide whether G admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor u ∊ is above and to the right of v, (ii) each neighbor u ∊ is above and to the left of v, (iii) each neighbor u ∊ is below and to the left of v, (iv) each neighbor u ∊ is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is -hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an O(n) × O(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

In this article, we define and study the new problem of S imultaneous PQ-O rdering . Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. S imultaneous PQ-O rdering asks whether orders of the leaves of each of the trees can be chosen simultaneously ; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that S imultaneous PQ-O rdering is NP -complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances . We show that this result serves as a framework for several other problems that can be formulated as instances of S imultaneous PQ-O rdering . In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for P artially PQ-C onstrained P lanarity for biconnected graphs, which asks for a planar embedding in the presence of PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for S imultaneous E mbedding with F ixed E dges for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.

Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem O ptimal F lex D raw that is defined as follows. Given a planar graph G on n vertices with maximum degree 4 ( 4-planar graph ) and for each edge e a cost function cost e : N 0 → R defining costs depending on the number of bends e has, compute a planar orthogonal drawing of G of minimum cost. In this generality O ptimal F lex D raw is NP-hard. We show that it can be solved efficiently if (1) the cost function of each edge is convex and (2) the first bend on each edge does not cause any cost. Our algorithm takes time O ( n , ⋅, T flow ( n ) and O ( n 2 , ⋅, T flow ( n )) for biconnected and connected graphs, respectively, where T flow ( n ) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.

Contraction hierarchies are a speed-up technique to improve the performance of shortest-path computations, which works very well in practice. Despite convincing practical results, there is still a lack of theoretical explanation for this behavior. In this paper, we develop a theoretical framework for studying search space sizes in contraction hierarchies. We prove the first bounds on the size of search spaces that depend solely on structural parameters of the input graph, that is, they are independent of the edge lengths. To achieve this, we establish a connection with the well-studied elimination game. Our bounds apply to graphs with treewidth k , and to any minor-closed class of graphs that admits small separators. For trees, we show that the maximum search space size can be minimized efficiently, and the average size can be approximated efficiently within a factor of 2. We show that, under a worst-case assumption on the edge lengths, our bounds are comparable to those in the recent paper “VC-Dimension and Shortest Path Algorithms” of Abraham et al. [1] , whose analysis depends also on the edge lengths. As a side result, we link their notion of highway dimension (a parameter that is conjectured to be small, but is unknown for all practical instances) with the notion of pathwidth. This is the first relation of highway dimension with a well-known graph parameter.

We study the following problem: given a planar graph G and a planar drawing (embedding) of a subgraph of G , can such a drawing be extended to a planar drawing of the entire graph G ? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time. Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problem Simultaneous Embedding with Fixed Edges (Sefe) . There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.

We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.

In this paper, we define and study the new problem Simultaneous PQ-Ordering. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. Simultaneous PQ-Ordering asks whether orders of the leaves of each of the trees can be chosen simultaneously, that is, for every child-parent relation the order chosen for the parent is an extension of the order chosen for the child. We show that Simultaneous PQ-Ordering is -complete in general and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of Simultaneous PQ-Ordering. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for Partially PQ-Constrained Planarity for biconnected graphs, which asks for a planar embedding in the presence of PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for Simultaneous Embedding with Fixed Edges for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two non-trivial blocks. This includes for example the case where both graphs have maximum degree 5.

Precomputation of auxiliary data in an additional off-line step is a common approach towards improving the performance of shortest-path queries in large-scale networks. One such technique is the arc-flags algorithm, where the preprocessing involves computing a partition of the input graph. The quality of this partition significantly affects the speed-up observed in the query phase. It is evaluated by considering the search-space size of subsequent shortest-path queries, in particular its maximum or its average over all queries. In this paper, we substantially strengthen existing hardness results of Bauer et al. and show that optimally filling this degree of freedom is NP-hard for trees with unit-length edges, even if we bound the height or the degree. On the other hand, we show that optimal partitions for paths can be computed efficiently and give approximation algorithms for cycles and trees.

A partially embedded graph (or PEG) is a triple (G,H,EH), where G is a graph, H is a subgraph of G, and EH is a planar embedding of H. We say that a PEG (G,H,EH) is planar if the graph G has a planar embedding that extends the embedding EH.

We study the following problem: Given a planar graph G and a planar drawing (embedding) of a subgraph of G, can such a drawing be extended to a planar drawing of the entire graph G? This problem fits the paradigm of extending a partial solution to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes hard an otherwise easy problem, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmata which show that the planarity of partially embedded graphs meets the “on-cas” behaviour – obvious necessary conditions for planarity are also sufficient. These conditions are expressed in terms of the interplay between (a) rotation schemes and containment relationships between cycles and (b) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently. Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we improve our algorithm to reach linear-time complexity. Finally, we consider several generalizations of the problem, e.g. minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. Also, we show how our algorithm can be applied to solve related Graph Drawing problems.

In this article we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in O (√ nm ) time, where n denotes the number of vertices and m the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3, the bounds we achieve are known to be best possible. We also investigate graphs with block trees of bounded degree, where the d -block tree is the adjacency graph of the d -connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute maximum matchings in slightly superlinear time.