BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Michael Kaufmann

Michael Kaufmann appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational GeometryData Structures and AlgorithmsDiscrete Mathematicsmath.COInformation Retrieval

Catalog footprint

What is connected

34works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

34 published item(s)

preprint2023arXiv

$k$-planar Placement and Packing of $Δ$-regular Caterpillars

This paper studies a \emph{packing} problem in the so-called beyond-planar setting, that is when the host graph is ``almost-planar'' in some sense. Precisely, we consider the case that the host graph is $k$-planar, i.e., it admits an embedding with at most $k$ crossings per edge, and focus on families of $Δ$-regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree $Δ$. We study the dependency of $k$ from the number $h$ of caterpillars that are packed, both in the case that these caterpillars are all isomorphic to one another (in which case the packing is called \emph{placement}) and when they are not. We give necessary and sufficient conditions for the placement of $h$ $Δ$-regular caterpillars and sufficient conditions for the packing of a set of $Δ_1$-, $Δ_2$-, $\dots$, $Δ_h$-regular caterpillars such that the degree $Δ_i$ and the degree $Δ_j$ of the non-leaf vertices can differ from one caterpillar to another, for $1 \leq i,j \leq h$, $i\neq j$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time

A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each vertex of G to a distinct point of the plane and each edge of $G$ to a sequence of horizontal and vertical segments between its end-points. A longstanding open question in Graph Drawing, dating back over 30 years, is whether there exists a linear-time algorithm to compute an orthogonal drawing of a plane 4-graph with the minimum number of bends. The term "plane" indicates that the input graph comes together with a planar embedding, which must be preserved by the drawing (i.e., the drawing must have the same set of faces as the input graph). In this paper, we positively answer the question above for the widely-studied class of series-parallel graphs. Our linear-time algorithm is based on a characterization of the planar series-parallel graphs that admit an orthogonal drawing without bends. This characterization is given in terms of the orthogonal spirality that each type of triconnected component of the graph can take; the orthogonal spirality of a component measures how much that component is "rolled-up" in an orthogonal drawing of the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Graph Product Structure for h-Framed Graphs

Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size $3\lfloor h/2 \rfloor +\lfloor h/3 \rfloor -1$. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 495 to 81 and from 32225k(k-3) to 61k, respectively. We also employ the product structure machinery to improve the current upper bounds of twin-width of planar and 1-planar graphs from 183 to 37, and from O(1) to 80, respectively. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

RAC Drawings of Graphs with Low Degree

Motivated by cognitive experiments providing evidence that large crossing-angles do not impair the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles. In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Lokahi Prototype: Toward the automatic Extraction of Entity Relationship Models from Text

Entity relationship extraction envisions the automatic generation of semantic data models from collections of text, by automatic recognition of entities, by association of entities to form relationships, and by classifying these instances to assign them to entity sets (or classes) and relationship sets (or associations). As a first step in this direction, the Lokahi prototype can extract entities based on the TF*IDF measure, and generate semantic relationships based on document-level co-occurrence statistics, for example with likelihood ratios and pointwise mutual information. This paper presents results of an explorative, prototypical, qualitative and synthetic research, summarizes insights from two research projects and, based on this, indicates an outline for further research in the field of entity relationship extraction from text.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time

A plane graph is rectilinear planar if it admits an embedding-preserving straight-line drawing where each edge is either horizontal or vertical. We prove that rectilinear planarity testing can be solved in optimal $O(n)$ time for any plane series-parallel graph $G$ with $n$ vertices. If $G$ is rectilinear planar, an embedding-preserving rectilinear planar drawing of $G$ can be constructed in $O(n)$ time. Our result is based on a characterization of rectilinear planar series-parallel graphs in terms of intervals of orthogonal spirality that their components can have, and it leads to an algorithm that can be easily implemented.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Four Pages Are Indeed Necessary for Planar Graphs

An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. Accordingly, the book thickness of a class of graphs is the maximum book thickness over all its members. In this paper, we address a long-standing open problem regarding the exact book thickness of the class of planar graphs, which previously was known to be either three or four. We settle this problem by demonstrating planar graphs that require four pages in any of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Lazy Queue Layouts of Posets

We investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w. The conjecture has been confirmed for posets of width w=2 via so-called lazy linear extension. We extend and thoroughly analyze lazy linear extensions for posets of width w > 2. Our analysis implies an upper bound of $(w-1)^2 +1$ on the queue number of width-w posets, which is tight for the strategy and yields an improvement over the previously best-known bound. Further, we provide an example of a poset that requires at least w+1 queues in every linear extension, thereby disproving the conjecture for posets of width w > 2.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Layered Fan-Planar Graph Drawings

In this paper, we study fan-planar drawings that use $h$ layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in $h$, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for $h=2$: It was already known how to test existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper $h$-layer drawings; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Low Ply Drawings of Trees

We consider the recently introduced model of \emph{low ply graph drawing}, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The \emph{ply-disk} of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the \emph{ply-number} of the drawing. We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree $6$ always admit such drawings in polynomial area.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Density of non-Simple 3-Planar Graphs

A \emph{$k$-planar graph} is a graph that can be drawn in the plane such that every edge is crossed at most $k$ times. For $k \leq 4$, Pach and Tóth proved a bound of $(k+3)(n-2)$ on the total number of edges of a $k$-planar graph, which is tight for $k=1,2$. For $k=3$, the bound of $6n-12$ has been improved to $\frac{11}{2}n-11$ and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of $\frac{11}{2}n-11$ edges also holds for non-simple $3$-planar graphs that admit drawings in which non-homotopic parallel edges and self-loops are allowed. Based on this result, a characterization of \emph{optimal $3$-planar graphs} (that is, $3$-planar graphs with $n$ vertices and exactly $\frac{11}{2}n-11$ edges) might be possible, as to the best of our knowledge the densest known simple $3$-planar is not known to be optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Planar Tree Packing Theorem

Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of García et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Vertex-Coloring with Star-Defects

Defective coloring is a variant of traditional vertex-coloring, according to which adjacent vertices are allowed to have the same color, as long as the monochromatic components induced by the corresponding edges have a certain structure. Due to its important applications, as for example in the bipartisation of graphs, this type of coloring has been extensively studied, mainly with respect to the size, degree, and acyclicity of the monochromatic components. In this paper we focus on defective colorings in which the monochromatic components are acyclic and have small diameter, namely, they form stars. For outerplanar graphs, we give a linear-time algorithm to decide if such a defective coloring exists with two colors and, in the positive case, to construct one. Also, we prove that an outerpath (i.e., an outerplanar graph whose weak-dual is a path) always admits such a two-coloring. Finally, we present NP-completeness results for non-planar and planar graphs of bounded degree for the cases of two and three colors.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Universal Point Set for 2-Outerplanar Graphs

A point set $S \subseteq \mathbb{R}^2$ is universal for a class $\cal G$ if every graph of ${\cal G}$ has a planar straight-line embedding on $S$. It is well-known that the integer grid is a quadratic-size universal point set for planar graphs, while the existence of a sub-quadratic universal point set for them is one of the most fascinating open problems in Graph Drawing. Motivated by the fact that outerplanarity is a key property for the existence of small universal point sets, we study 2-outerplanar graphs and provide for them a universal point set of size $O(n \log n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Contact Representations of Sparse Planar Graphs

We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is realized by an endpoint of one arc touching the interior of another. A graph is (2,k)-sparse if every s-vertex subgraph has at most 2s - k edges, and (2, k)-tight if in addition it has exactly 2n - k edges, where n is the number of vertices. Every graph with a CCA- representation is planar and (2, 0)-sparse, and it follows from known results on contacts of line segments that for k >= 3 every (2, k)-sparse graph has a CCA-representation. Hence the question of CCA-representability is open for (2, k)-sparse graphs with 0 <= k <= 2. We partially answer this question by computing CCA-representations for several subclasses of planar (2,0)-sparse graphs. In particular, we show that every plane (2, 2)-sparse graph has a CCA-representation, and that any plane (2, 1)-tight graph or (2, 0)-tight graph dual to a (2, 3)-tight graph or (2, 4)-tight graph has a CCA-representation. Next, we study CCA-representations in which each arc has an empty convex hull. We characterize the plane graphs that have such a representation, based on the existence of a special orientation of the graph edges. Using this characterization, we show that every plane graph of maximum degree 4 has such a representation, but that finding such a representation for a plane (2, 0)-tight graph with maximum degree 5 is an NP-complete problem. Finally, we describe a simple algorithm for representing plane (2, 0)-sparse graphs with wedges, where each vertex is represented with a sequence of two circular arcs (straight-line segments).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Contact Graphs with Cubes and Proportional Boxes

We study two variants of the problem of contact representation of planar graphs with axis-aligned boxes. In a cube-contact representation we realize each vertex with a cube, while in a proportional box-contact representation each vertex is an axis-aligned box with a prespecified volume. We present algorithms for constructing cube-contact representation and proportional box-contact representation for several classes of planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Embeddability of Buses in Point Sets

Set membership of points in the plane can be visualized by connecting corresponding points via graphical features, like paths, trees, polygons, ellipses. In this paper we study the \emph{bus embeddability problem} (BEP): given a set of colored points we ask whether there exists a planar realization with one horizontal straight-line segment per color, called bus, such that all points with the same color are connected with vertical line segments to their bus. We present an ILP and an FPT algorithm for the general problem. For restricted versions of this problem, such as when the relative order of buses is predefined, or when a bus must be placed above all its points, we provide efficient algorithms. We show that another restricted version of the problem can be solved using 2-stack pushall sorting. On the negative side we prove the NP-completeness of a special case of BEP.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Total Number of Bends for Planar Octilinear Drawings

An octilinear drawing of a planar graph is one in which each edge is drawn as a sequence of horizontal, vertical and diagonal at 45 degrees line-segments. For such drawings to be readable, special care is needed in order to keep the number of bends small. As the problem of finding planar octilinear drawings of minimum number of bends is NP-hard, in this paper we focus on upper and lower bounds. From a recent result of Keszegh et al. on the slope number of planar graphs, we can derive an upper bound of 4n-10 bends for 8-planar graphs with n vertices. We considerably improve this general bound and corresponding previous ones for triconnected 4-, 5- and 6-planar graphs. We also derive non-trivial lower bounds for these three classes of graphs by a technique inspired by the network flow formulation of Tamassia.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Book Thickness of 1-Planar Graphs is Constant

In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges on the same page do not cross. In this paper, we prove that every $1$-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is $O(\sqrt{n})$, where $n$ is the number of vertices of the graph.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs

Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a polynomial-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-hard, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Maximum k-Differential Coloring Problem

Given an $n$-vertex graph $G$ and two positive integers $d,k \in \mathbb{N}$, the ($d,kn$)-differential coloring problem asks for a coloring of the vertices of $G$ (if one exists) with distinct numbers from 1 to $kn$ (treated as \emph{colors}), such that the minimum difference between the two colors of any adjacent vertices is at least $d$. While it was known that the problem of determining whether a general graph is ($2,n$)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit ($2,kn$)-differential colorings. For practical reasons, we consider also color ranges larger than $n$, i.e., $k > 1$. We show that it is NP-complete to determine whether a graph admits a ($3,2n$)-differential coloring. The same negative result holds for the ($\lfloor 2n/3 \rfloor, 2n$-differential coloring problem, even in the case where the input graph is planar.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs

A graph is called a strong (resp. weak) bar 1-visibility graph if its vertices can be represented as horizontal segments (bars) in the plane so that its edges are all (resp. a subset of) the pairs of vertices whose bars have a $ε$-thick vertical line connecting them that intersects at most one other bar. We explore the relation among weak (resp. strong) bar 1-visibility graphs and other nearly planar graph classes. In particular, we study their relation to 1-planar graphs, which have a drawing with at most one crossing per edge; quasi-planar graphs, which have a drawing with no three mutually crossing edges; the squares of planar 1-flow networks, which are upward digraphs with in- or out-degree at most one. Our main results are that 1-planar graphs and the (undirected) squares of planar 1-flow networks are weak bar 1-visibility graphs and that these are quasi-planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Many-to-One Boundary Labeling with Backbones

In this paper we study \emph{many-to-one boundary labeling with backbone leaders}. In this new many-to-one model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points that need to be connected to this label are linked via vertical line segments to the backbone. We present dynamic programming algorithms for label number and total leader length minimization of crossing-free backbone labelings. When crossings are allowed, we aim to obtain solutions with the minimum number of crossings. This can be achieved efficiently in the case of fixed label order, however, in the case of flexible label order we show that minimizing the number of leader crossings is NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Smooth Orthogonal Drawings of Planar Graphs

In \emph{smooth orthogonal layouts} of planar graphs, every edge is an alternating sequence of axis-aligned segments and circular arcs with common axis-aligned tangents. In this paper, we study the problem of finding smooth orthogonal layouts of low \emph{edge complexity}, that is, with few segments per edge. We say that a graph has \emph{smooth complexity} k---for short, an SC_k-layout---if it admits a smooth orthogonal drawing of edge complexity at most $k$. Our main result is that every 4-planar graph has an SC_2-layout. While our drawings may have super-polynomial area, we show that, for 3-planar graphs, cubic area suffices. Further, we show that every biconnected 4-outerplane graph admits an SC_1-layout. On the negative side, we demonstrate an infinite family of biconnected 4-planar graphs that requires exponential area for an SC_1-layout. Finally, we present an infinite family of biconnected 4-planar graphs that does not admit an SC_1-layout.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Threshold-Coloring and Unit-Cube Contact Representation of Graphs

In this paper we study threshold coloring of graphs, where the vertex colors represented by integers are used to describe any spanning subgraph of the given graph as follows. Pairs of vertices with near colors imply the edge between them is present and pairs of vertices with far colors imply the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs without short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. Variants of the threshold coloring problem are related to well-known graph coloring and other graph-theoretic problems. Using these relations we show the NP-completeness for two of these variants, and describe a polynomial-time algorithm for another.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximating Minimum Manhattan Networks in Higher Dimensions

We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called \emph{terminals} in $\R^d$, find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, $L_1$-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless ${\cal P}={\cal NP}$). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension $d$ and any $\eps>0$, an $O(n^\eps)$-approximation algorithm. For 3D, we also give a $4(k-1)$-approximation algorithm for the case that the terminals are contained in the union of $k \ge 2$ parallel planes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Progress on Partial Edge Drawings

Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction $δ$ of the edge lengths ($δ$-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. We show that, for a fixed stub--edge length ratio $δ$, not all graphs have a $δ$-SHPED. Specifically, we show that $K_{241}$ does not have a 1/4-SHPED, while bandwidth-$k$ graphs always have a $Θ(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons and edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight of the corresponding vertex. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine the representation into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal rectangular layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal Polygonal Representation of Planar Graphs

In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes and with all vertices lying on an O(n)xO(n) grid.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Upward Point Set Embeddability for Convex Point Sets is in $P$

In this paper, we present a polynomial dynamic programming algorithm that tests whether a $n$-vertex directed tree $T$ has an upward planar embedding into a convex point-set $S$ of size $n$. Further, we extend our approach to the class of outerplanar digraphs. This nontrivial and surprising result implies that any given digraph can be efficiently tested for an upward planar embedding into a given convex point set.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On a Tree and a Path with no Geometric Simultaneous Embedding

Two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ admit a geometric simultaneous embedding if there exists a set of points P and a bijection M: P -> V that induce planar straight-line embeddings both for $G_1$ and for $G_2$. While it is known that two caterpillars always admit a geometric simultaneous embedding and that two trees not always admit one, the question about a tree and a path is still open and is often regarded as the most prominent open problem in this area. We answer this question in the negative by providing a counterexample. Additionally, since the counterexample uses disjoint edge sets for the two graphs, we also negatively answer another open question, that is, whether it is possible to simultaneously embed two edge-disjoint trees. As a final result, we study the same problem when some constraints on the tree are imposed. Namely, we show that a tree of depth 2 and a path always admit a geometric simultaneous embedding. In fact, such a strong constraint is not so far from closing the gap with the instances not admitting any solution, as the tree used in our counterexample has depth 4.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Upward Point-Set Embeddability

We study the problem of Upward Point-Set Embeddability, that is the problem of deciding whether a given upward planar digraph $D$ has an upward planar embedding into a point set $S$. We show that any switch tree admits an upward planar straight-line embedding into any convex point set. For the class of $k$-switch trees, that is a generalization of switch trees (according to this definition a switch tree is a $1$-switch tree), we show that not every $k$-switch tree admits an upward planar straight-line embedding into any convex point set, for any $k \geq 2$. Finally we show that the problem of Upward Point-Set Embeddability is NP-complete.

0 citations0 reviewsNo code linkedOpen access