A dominating set of a graph G is connected if it induces a connected graph in G. For planar triangulations, it has been known since 1990 that every n-vertex triangulation admits a connected dominating set of size at most n/2 - 1, and no improvement to this bound was known for over three decades. We break this longstanding barrier by showing that every n-vertex triangulation has a connected dominating set of size at most 10n/21. Equivalently, every triangulation admits a spanning tree with at least 11n/21 leaves. Moreover, we present an algorithm that computes such a set in optimal linear time. Our result narrows the gap to the best known lower bound and has graph drawing applications, establishing a bound for one-bend free sets and improving the known bound for simultaneous planar embeddings.

We show that every n-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order ). Equivalently, every n-vertex planar graph G has a set X of ) vertices such that G — X has bandwidth ). This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and k-planar graphs for fixed k. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every n-vertex planar graph G has a set of O ((n log n )/D ) vertices whose removal results in a graph with local density at most D. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings.

The crossing number of a graph $G$ is the minimum number of crossings in a drawing of $G$ in the plane. A rectilinear drawing of a graph $G$ represents vertices of $G$ by a set of points in the plane and represents each edge of $G$ by a straight-line segment connecting its two endpoints. The rectilinear crossing number of $G$ is the minimum number of crossings in a rectilinear drawing of $G$. By the crossing lemma, the crossing number of an $n$-vertex graph $G$ can be $O(n)$ only if $|E(G)|\in O(n)$. Graphs of bounded genus and bounded degree (Böröczky, Pach and Tóth, 2006) and in fact all bounded degree proper minor-closed families (Wood and Telle, 2007) have been shown to admit linear crossing number, with tight $Θ(Δn)$ bound shown by Dujmović, Kawarabayashi, Mohar and Wood, 2008. Much less is known about rectilinear crossing number. It is not bounded by any function of the crossing number. We prove that graphs that exclude a single-crossing graph as a minor have the rectilinear crossing number $O(Δn)$. This dependence on $n$ and $Δ$ is best possible. A single-crossing graph is a graph whose crossing number is at most one. Thus the result applies to $K_5$-minor-free graphs, for example. It also applies to bounded treewidth graphs, since each family of bounded treewidth graphs excludes some fixed planar graph as a minor. Prior to our work, the only bounded degree minor-closed families known to have linear rectilinear crossing number were bounded degree graphs of bounded treewidth (Wood and Telle, 2007), as well as, bounded degree $K_{3,3}$-minor-free graphs (Dujmović, Kawarabayashi, Mohar and Wood, 2008). In the case of bounded treewidth graphs, our $O(Δn)$ result is again tight and improves on the previous best known bound of $O(Δ^2 n)$ by Wood and Telle, 2007 (obtained for convex geometric drawings).

We prove that for every planar graph X of treedepth h, there exists a positive integer c such that for every X-minor-free graph G, there exists a graph H of treewidth at most f (h) such that G is isomorphic to a subgraph of H ⊠ Kc. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB, 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a given graph as a minor.

Abstract. Alon, Seymour, and Thomas [ J. Amer. Math. Soc., 3 (1990), pp. 801–808] proved that every [Formula: see text]-vertex graph excluding [Formula: see text] as a minor has treewidth less than [Formula: see text]. Illingworth, Scott, and Wood [ Product Structure of Graphs with an Excluded Minor, preprint, arXiv:2104.06627 , 2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth [Formula: see text], where each vertex is blown up by a complete graph of order [Formula: see text]. Solving an open problem of Illingworth, Scott, and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order [Formula: see text]. As an extension of the Lipton–Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalize this result for [Formula: see text]-minor-free graphs, with blowups of order [Formula: see text]. This setting includes graphs embeddable on any fixed surface.

Abstract. This is a corrigendum for the article “Orthogonal Tree-Decompositions of Graphs” [SIAM J. Discrete Math. 32(2):839–863, 2018].

Hadwiger’s Conjecture asserts that every $K_{h}$-minor-free graph is properly $(h-1)$-colourable. We prove the following improper analogue of Hadwiger’s Conjecture: for fixed h, every $K_{h}$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $t \geqslant s$, we show that every $K_{s, t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van den Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, we strengthen the result as follows: for fixed $t \geqslant s \geqslant 3$, and for any fixed apex graph X, every $K_{s, t}$-subgraph-free X-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible.

We show that, if an n-vertex triangulation G of maximum degree $$\Delta $$ has a dual that contains a cycle of length $$\ell $$ , then G has a non-crossing straight-line drawing in which some set, called a collinear set, of $$\Omega (\ell /\Delta ^4)$$ vertices lie on a line. Using the current lower bounds on the length of longest cycles in cubic 3-connected graphs, this implies that every n-vertex planar graph of maximum degree $$\Delta $$ has a collinear set of size $$\Omega (n^{0.8}/\Delta ^4)$$ .

We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses $$O(n^2)$$ pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n -vertex planar graph G is assigned a (1 + o(1)) log 2 n -bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G . This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n , there exists a graph U n with n 1+o(1) vertices such that every n -vertex planar graph is an induced subgraph of U n . These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k -planar graphs.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n-vertex planar graph G is assigned a (1+o(1))log2n-bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n, there exists a graph Un with n1+o(1)vertices such that every n-vertex planar graph is an induced subgraph of Un. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions , and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. [31] that graphs in a proper minor-closed class have low treewidth colourings.

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number. Layered partitions can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes.

We show that if a planar graph G has a plane straight-line drawing in which a subset S of its vertices are collinear, then for any set of points, X, in the plane with |X| = |S|, there is a plane straight-line drawing of G in which the vertices in S are mapped to the points in X. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings.

An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi [Therese C. Biedl and Saeed Mehrabi, 2017] studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the L_1 (Manhattan) shortest paths in the plane that avoid obstacles. In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.

This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here “linear size” means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.

The following is a corrigendum to [ Orthogonal tree decompositions of graphs, SIAM J. Discrete Math., 32 (2018), pp. 839--863].

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an $n$-vertex graph embedded on a surface of genus $g$ with at most $k$ crossings per edge has treewidth $O(\sqrt{(g+1)(k+1)n})$ and layered treewidth $O((g+1)k)$ and that these bounds are tight up to a constant factor. In the special case of $g=0$, so-called $k$-planar graphs, the treewidth bound is $O(\sqrt{(k+1)n})$, which is tight and improves upon a known $O((k+1)^{3/4}n^{1/2})$ bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for $g

It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors. For fixed $g$ and $k$, we show that every $n$-vertex graph that can be embedded on a surface of genus $g$ with at most $k$ crossings per edge has stack-number $\mathcal{O}(\log n)$; this includes $k$-planar graphs. The previously best known bound for the stack-number of these families was $\mathcal{O}(\sqrt{n})$, except in the case of $1$-planar graphs. Analogous results are proved for map graphs that can be embedded on a surface of fixed genus. None of these families is closed under taking minors. The main ingredient in the proof of these results is a construction proving that $n$-vertex graphs that admit constant layered separators have $\mathcal{O}(\log n)$ stack-number.

In this note we show how techniques developed for untangling planar graphs by Bose et al. [Discrete & Computational Geometry 42(4): 570-585 (2009)] and Goaoc et al. [Discrete & Computational Geometry 42(4): 542-569 (2009)] imply new results about some recent graph drawing models. These include column planarity, universal point subsets, and partial simultaneous geometric embeddings (with or without mappings). Some of these results answer open problems posed in previous papers.

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth $$O(\sqrt{(g+1)(k+1)n})$$ and layered treewidth $$O((g+1)k)$$ , and that these bounds are tight up to a constant factor. As a special case, the k-planar graphs with n vertices have treewidth $$O(\sqrt{(k+1)n})$$ and layered treewidth $$O(k+1)$$ , which are tight bounds that improve a previously known $$O((k+1)^{3/4}n^{1/2})$$ treewidth bound. Additionally, we show that for $$g

Motivated by applications to graph morphing, we consider the following compatible connectivity-augmentation problem: We are given a labelled n-vertex planar graph, G, that has r ≥ 2 connected components, and k ≥ 2 isomorphic planar straight-line drawings, G1, …, G2, of G. We wish to augment G by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to G1, …, G2 as points and straight-line segments, respectively, to obtain k planar straight-line drawings isomorphic to the augmentation of G. We show that adding Θ(nr1–1/k) edges and vertices to G is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all r ∊ {2, …, n} and k ≥ 2 and is achievable by an algorithm whose running time is O(nr1–1/k) for k = O(1) and whose running time is O(kn2) for general values of k. The lower bound holds for all r ∊ {2, …, n/4} and k ≥ 2.

An empty pentagon in a point set $P$ in the plane is a set of five points in $P$ in strictly convex position with no other point of $P$ in their convex hull. We prove that every finite set of at least $328\ell^2$ points in the plane contains an empty pentagon or $\ell$ collinear points. This is optimal up to a constant factor since the $(\ell -1)\times(\ell-1)$ square lattice contains no empty pentagon and no $\ell$ collinear points. The previous best known bound was doubly exponential.

Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely a pplicable and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.

Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator can be as large as Ω(√n) in graphs with n vertices. This is the case for planar graphs, and more generally, for proper minor-closed families. We study a special type of graph separator, called a layered separator, which may have linear size in n, but has bounded size with respect to a different measure, called the breadth. We prove that a wide class of graphs admit layered separators of bounded breadth, including graphs of bounded Euler genus. We use layered separators to prove Õ(log n) bounds for a number of problems where O(√n) was a long standing previous best bound. This includes the nonrepetitive chromatic number and queue-number of graphs with bounded Euler genus. We extend these results to all proper minor-closed families, with a O(log n) bound on the nonrepetitive chromatic number, and a logO(1)n bound on the queue-number. Only for planar graphs were logO(1)n bounds previously known. Our results imply that every graph from a proper minor-closed class has a 3-dimensional grid drawing with n logO(1)n volume, whereas the previous best bound was O(n3/2). Readers interested in the full details should consult arXiv:1302.0304 and arXiv:1306.1595, rather than the current extended abstract.

Highly connected and yet sparse graphs (such as expanders or graphs of high treewidth) are fundamental, widely applicable, and extensively studied combinatorial objects. We initiate the study of such highly connected graphs that are, in addition, geometric spanners. We define a property of spanners called robustness. Informally, when one removes a few vertices from a robust spanner, this harms only a small number of other vertices. We show that robust spanners must have a superlinear number of edges, even in one dimension. On the positive side, we give constructions, for any dimension, of robust spanners with a near-linear number of edges.

Let $g(t)$ be the minimum number such that every graph $G$ with average degree $d(G) \geq g(t)$ contains a $K_{t}$-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that $g(t) \in \Theta(t\sqrt{\log t})$. This paper shows that for all fixed $\epsilon > 0$ and fixed sufficiently large $t \geq t(\epsilon)$, if $d(G) \geq (2+\epsilon)g(t)$, then we can find this $K_{t}$-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when $d(G) \geq 2^{t-2}$.

We propose a new k-NN regression estimate based on a data-dependent metric in Rdwhich is used to define the k-nearest neighbors of a given point. The metric is invariant under all affine transformations. With this metric, the standard k-nearest neighbor regression estimate is asymptotically consistent under the usual conditions on k, and minimal requirements on the input data.

It is known that the First-Fit algorithm for partitioning a poset $P$ into chains uses relatively few chains when $P$ does not have two incomparable chains each of size $k$. In particular, if $P$ has width $w$, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992--1999], proved an upper bound of $ckw^{2}$ on the number of chains used by First-Fit for some constant $c$, while Joret and Milans [Order, 28 (2011), pp. 455--464] gave one of $ck^{2}w$. In this paper we prove an upper bound of the form $ckw$. This is most possible up to the value of $c$.

A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G . The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D , is H˜ + O (H˜ 1/2 +1) where H˜=H˜( G,D ) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in G under the query distribution D . The preprocessing algorithm runs in O ( n log n ) time and produces a data structure of size O ( n ). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.

Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in R2, there is a line l such that in both line sets, for both halfplanes delimited by l, there are √n lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of n lines there is a point such that for any halfplane containing that point there are √n/3 of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erdos-Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to Graph Drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labelled lines that are universal for all n-vertex labelled planar graphs. As a side note, we prove that every set of n (unlabelled) lines is universal for all n-vertex (unlabelled) planar graphs.

A data structure, called a biased range tree, is presented that preprocesses a set S of n points in ℝ2 and a query distribution D for 2-sided orthogonal range counting queries. The expected query time for this data structure, when queries are drawn according to D, matches, to within a constant factor, that of the optimal comparison tree for S and D. The memory and preprocessing requirements of the data structure are O(n log n).

The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has crossing number O(Δn), where G has n vertices and maximum degree Δ. This dependence on n and Ø is best possible. This result answers an open question of Wood and Telle [New York J. Mathematics, 2007], who proved the best previous bound of O(Ø2n).

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in $\mathbb{R}^3$ with a total of n edges consists of $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrarily degenerate scenes. More generally, we show that a set of k possibly intersecting convex polyhedra with a total of n edges admits, in the worst case, $\Theta(n^2k^2)$ connected components of maximal free line segments tangent to at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present an $O(n^2 k^2 \log n)$ time and $O(nk^2)$ space algorithm that, given a scene of k possibly intersecting convex polyhedra, computes all the minimal free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.

Aqueue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its queue-number. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in $\mathbb{Z}^3$ and the edges by noncrossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph G is closely related to the queue-number of G. In particular, if G is an n-vertex member of a proper minor-closed family of graphs (such as a planar graph), then G has a $\mathcal{O}(1) \times \mathcal{O}(1) \times \mathcal{O}(n)$ drawing if and only if G has a $\mathcal{O}(1)$ queue-number. (2) It is proved that the queue-number is bounded by the tree-width, thus resolving an open problem due to Ganley and Heath [Discrete Appl. Math., 109 (2001), pp. 215--221] and disproving a conjecture of Pemmaraju [Exploring the Powers of Stacks and Queues via Graph Layouts, Ph. D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1992]. This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with $\mathcal{O}(n)$ volume. This is the most general family of graphs known to admit three-dimensional drawings with $\mathcal{O}(n)$ volume. The proofs depend upon our results regarding track layouts and tree-partitions of graphs, which may be of independent interest.

We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝ3 with n edges in total form Θ(n2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of kconvex polyhedra with a total of n edges admits, in the worst case, Θ(n2k2)connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

In this paper, we show that, amongst n uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176-206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

We consider the robot exploration of a planar graph-like world. The robot's goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph which is initially unknown to the robot. The robot cannot distinguish vertices and edges that it has explored from the unexplored ones. The robot is assumed to be able to autonomously traverse graph edges, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex. The robot cannot measure distances nor does it have a compass, but it is equipped with a single marker that it can leave at a vertex and sense if the marker is present at a newly visited vertex. The total number of edges traversed while constructing a map of a graph is used as a measure of performance. We present an efficient algorithm for learning an unknown, undirected planar graph by a robot equipped with one marker. Experimental results obtained by running a large collection of example worlds are presented.