Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUpward Partitioned Book Embeddings
385
0
0.0
(
0
)
Added by
Quanquan C. Liu
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding). Given a directed acyclic graph and a partition of its edges into $k$ pages, can we linearly order the vertices such that the drawing is upward (a topological sort) and each page avoids crossings? We prove that the problem is NP-complete for $kge 3$, and for $kge 4$ even in the special case when each page is a matching. By contrast, the problem can be solved in linear time for $k=2$ pages when pages are restricted to matchings. The problem comes from Jack Edmonds (1997), motivated as a generalization of the map folding problem from computational origami.
rate research
Read More
We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $kgeq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $beta$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(beta)cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $beta$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE.
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are $at$-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness $k$ is NP-hard for any fixed $k ge 3$. We show that the problem, for any $k ge 5$, remains NP-hard for graphs whose domination number is $O(k)$, but it is FPT in the vertex cover number.
This paper studies the problem of computing quasi-upward planar drawings of bimodal plane digraphs with minimum curve complexity, i.e., drawings such that the maximum number of bends per edge is minimized. We prove that every bimodal plane digraph admits a quasi-upward planar drawing with curve complexity two, which is worst-case optimal. We also show that the problem of minimizing the curve complexity in a quasi-upward planar drawing can be modeled as a min-cost flow problem on a unit-capacity planar flow network. This gives rise to an $tilde{O}(m^frac{4}{3})$-time algorithm that computes a quasi-upward planar drawing with minimum curve complexity; in addition, the drawing has the minimum number of bends when no edge can be bent more than twice. For a contrast, we show bimodal planar digraphs whose bend-minimum quasi-upward planar drawings require linear curve complexity even in the variable embedding setting.
Given $n$ pairs of points, $mathcal{S} = {{p_1, q_1}, {p_2, q_2}, dots, {p_n, q_n}}$, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.
The Possible-Winner problem asks, given an election where the voters preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of Possible-Winner under the assumption that the voter preferences are $partitioned$. That is, we assume that every voter provides a complete order over sets of incomparable candidates (e.g., candidates are ranked by their level of education). We consider elections with partitioned profiles over positional scoring rules, with an unbounded number of candidates, and unweighted voters. Our first result is a polynomial time algorithm for voting rules with $2$ distinct values, which include the well-known $k$-approval voting rule. We then go on to prove NP-hardness for a class of rules that contain all voting rules that produce scoring vectors with at least $4$ distinct values.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
