Testing Bipartiteness of Geometric Intersection Graphs
David Eppstein
Abstract We show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of balls in Rd , in time O(n log n). More generally we find subquadratic algorithms for connectivity and bipartiteness testing of intersection graphs of a broad class of geometric ob jects. For unit balls in Rd , connectivity testing has equivalent randomized complexity to construction of Euclidean minimum spanning trees, and for line segments in the plane connectivity testing has the same lower bounds as Hopcroft's problem; therefore, for these problems, connectivity is unlikely to be solved as efficiently as bipartiteness. For line segments or planar disks, testing k -colorability of intersection graphs for k > 2 is NP-complete. 1 Intro duction Suppose we are given a collection of geometric ob jects, for instance line segments in the plane. Can we partition them into a small number of subsets, such that within each subset the ob jects are disjoint from each other? This geometric problem can be modeled graph-theoretically as that of coloring an intersection graph. For three or more colors, graph coloring is NPcomplete, and remains so for many natural classes of intersection graph. But what if we wish to partition the input into only two non-self-intersecting subsets? Testing bipartiteness for graphs can easily be solved in linear time, but for geometric ob jects, the corresponding graph bipartiteness instance may have quadratic size, so constructing the graph and then testing it could take time quadratic in the number of input ob jects. Can we do better? The motivation for our study comes from graph drawing, specifically geometric thickness [8, 9, 29], also known as real linear thickness [22], or, in the case of geometric thickness two, doubly-linear graphs [19]. A drawing of a graph, for our purposes, consists of an assignment of the graph's vertices to points in the plane, and its edges to simple plane curves connecting these points, such that no vertex lies on an edge unless it is an endpoint of that edge. A straight Scho ol of Information and Computer Science, University of California, Irvine, CA 92697-3425, USA, eppstein@ics.uci.edu

line drawing is a drawing in which all the edges are drawn as line segments. The thickness of a drawing is the minimum number of subsets into which the graph's edges can be partitioned such that, within any subset, no two edges are drawn as curves that cross each other. Alternatively, we can imagine assigning colors to the edges in a drawing, such that each color class forms a planar drawing. A graph's thickness [22] is equal to the minimum thickness of any drawing of the given graph, while its geometric thickness is the minimum thickness of any straight-line drawing. Figure 1 shows thickness-two straight-line drawings of two complete bipartite graphs; these graphs are non-planar, so their geometric thickness is two. The color separation between crossing edges in low-thickness drawings may reduce visual ambiguity when following connections between vertices. We would like to include in the graph drawing repertoire procedures for finding low-thickness drawings of graphs. However, determining the thickness of a graph is NP-complete, even for thickness two [24]. We can not yet prove a similar NP-completeness result for geometric thickness but it seems likely to be true as well. Since exact computation of geometric thickness appears to have high computational complexity, we are led to other procedures: either interactive drawing processes in which a human operator adjusts vertex placements in an attempt to reduce the drawing's thickness, or heuristic search procedures for finding low-thickness placements. In either case, in order to implement these procedures, we must test the thickness of individual drawings of graphs. This thickness testing problem, for thickness two, is exactly the bipartiteness problem for the line segment arrangement formed by the drawing's edges. Partitions into few non-crossing subsets may have other algorithmic uses as well. For instance, vertical ray shooting in arrangements of non-crossing line segments can be performed in logarithmic time and linear space by point location in the trapezoidal decomposition of the segments, while achieving the same query time for arrangements of crossing line segments seems to require quadratic space. If the arrangement can be partitioned into few non-crossing subsets, a vertical ray shooting query can be handled by combining independent query

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

860


Figure 1: Thickness-two straight-line drawing of K6,6 (left) and K5,8 (right). The partitions of the drawings' edges into two non-crossing subsets are indicated by solid and dashed line segments. results within each subset, providing a significant space savings. Formally, the problem we are interested in solving is the following. Given a collection of geometric objects, their intersection graph is an undirected graph that has one vertex per ob ject, and connects two objects by an edge whenever the intersection of the two ob jects is nonempty. We wish to determine whether the intersection graph is bipartite, and if so to find a two-coloring of this graph. In the case of geometric thickness, the ob jects we are interested in are the edges of the drawing (that is, they form an arrangement of open line segments) and we wish to test the bipartiteness of the intersection graph of these line segments. It may be of interest in other applications to test bipartiteness of other intersection graphs such as those of disks or rectangles. For many types of ob jects, including line segments, disks, and rectangles, algorithms are known that can construct the intersection graph in time that matches or nearly matches the output size [5, 11]. One could then apply any linear-time graph bipartiteness algorithm to the intersection graph. However, in the worst case these graphs can have quadratic size; for instance in the graph thickness problem, it may be common to have many nearly-horizontal segments in one layer and many nearly-vertical segments in another layer, creating a large number of crossings. We are interested here in improving on this naive approach, and achieving subquadratic or even near-linear complexity bounds for the intersection graph bipartiteness problem. Curiously, while for graphs connectivity is somewhat simpler than bipartiteness, for geometric intersection graphs the situation seems to be reversed: only one of our bipartiteness testing algorithms extends directly to connectivity. We provide evidence that, for unit balls in dimensions greater than two, bipartiteness testing is strictly easier than connectivity, by showing an equivalence between connectivity testing and Euclidean minimum spanning trees. For planar line segments, also, our bipartiteness testing algorithm has time bounds significantly smaller than lower bounds on connectivity testing derived by a reduction from Hopcroft's problem on point-line incidences [12]. 2 New Results We provide the following new results: · We describe a generic technique that, for most classes of geometric ob jects with bounded description complexity, leads to subquadratic times for testing the bipartiteness or listing the connected components of the ob jects' intersection graphs. · We provide an O(n log n) time algorithm for testing bipartiteness of n balls in Rd . We also use a randomized reduction to show that testing connectivity of unit balls is equivalent in complexity to constructing Euclidean minimum spanning trees, and therefore is unlikely to have near-linear algorithms in dimensions higher than two. · We give an O(n log n) time algorithm for testing bipartiteness of n line segments in the plane, or of a collection of simple polygons with n total edges.

861


forest. At each step of the depth first search we maintain a decremental intersection detection data structure representing the ob jects that have not yet been visited in the search; initially this consists of all the ob jects in the input. When the search reaches a previously un· We construct reductions proving the NPvisited ob ject x, we add x to the spanning forest, recompleteness of testing the 3-colorability of move x from the intersection detection data structure, intersection graphs for line segments or unit disks repeatedly use the intersection detection data structure in the plane. to find unvisited ob jects intersecting x, and recursively While there has been some prior work on connec- visit each such ob ject. Each query either leads to a new tivity of geometric intersection graphs [15­17, 20, 21], we visited ob ject or is the last query for x, so the algorithm are unaware of prior work on intersection graph bipar- makes fewer than 2n total queries and the running time is as stated. 2 titeness. 3 Generic Bipartiteness Algorithm In this section we describe a generic approach to intersection graph bipartiteness testing, that works for a wide class of geometric ob jects. In a graph bipartiteness algorithm based on a graph traversal algorithm such as depth first or breadth first search, most of the time is spent traversing edges between already-visited ob jects. It is natural, then, to hope to speed up this approach in the geometric setting by using data structures to quickly find only those ob jects that have not yet been visited in the traversal. We define an intersection detection data structure for a set S of ob jects to be one which, given a query consisting of an ob ject x of the same type as the ones in S , can quickly find and return an ob ject in S that intersects x, if one exists. An intersection detection data structure is decremental if it supports deletion operations that remove a specified ob ject from S , so that subsequent queries will not return the deleted ob ject. We measure the time complexity of a decremental intersection detection data structure D by two functions: QD (n), measuring the amortized time per query when the size of the set of ob jects is n, and TD (n), measuring the time to set up a data structure for and then delete in worst-case order all the ob jects in a set of n ob jects. For most natural classes of geometric ob ject with bounded description complexity, standard range searching techniques [2] can be used to provide decremental intersection detection data structures where TD (n) = O(n2-c ) and QD (n) = O(n1-c ) for some constant c > 0 that depends only on the ob ject type. Theorem 3.1. Let C be a class of objects having a decremental intersection detection data structure D with TD (n) = O(n2-c ) and QD (n) = O(n1-c ). Then in time O(n2-c ) we can construct a spanning forest for the intersection graph of any set of n objects in class C . Proof. We perform a depth first search of the intersection graph, and return the resulting depth first spanning Theorem 3.2. Let C be a class of objects having a decremental intersection detection data structure D with TD (n) = O(n2-c ) and QD (n) = O(n1-c ). Then in time O(n2-c ) we can test the bipartiteness of an intersection graph of any set of n objects in class C , and return either a two-coloring of the intersection graph or an odd cycle. Proof. We first apply the spanning forest algorithm above, and use it to two-color the ob jects, using one color for ob jects at even height in the forest and the other color for ob jects at odd height. To test the validity of the resulting coloring, we search for intersections within each color class, by applying the spanning forest algorithm separately to each color class and testing for the existence of any nontrivial trees. If no two ob jects of the same color intersect, we return the coloring. If two ob jects x and y having the same color intersect, then x and y must be within the same tree of the overall spanning forest, and an odd cycle in the intersection graph can be found by adding edge xy to the spanning forest path connecting x to y . 2 We view this generic bipartiteness testing algorithm as a baseline for further algorithmic improvements. As we shall see in subsequent sections, it can be significantly improved in certain cases, including balls in Rd and line segments in the plane. 4 Bipartiteness for Balls We now describe an alternative approach for testing bipartiteness for the intersection graphs of balls in Rd , in O(n log n) time for any fixed dimension. We then provide a randomized reduction showing the equivalence (to within polylogarithmic factors) of the problems of Euclidean minimum spanning trees and connected components of unions of unit balls, showing that a similarly fast time bound for connectivity is unlikely. The basic idea of our bipartiteness algorithm is that, while ball intersection graphs in general can be dense, bipartite ball intersection graphs must be sparse. More

However, finding the connected components of line segments is at least as hard as Hopcroft's problem and is therefore unlikely to have as efficient an algorithm.

862


b´

b0

bi

Figure 2: Balls b0 , b , and bi from the proof of Lemma 4.1. generally, similar sparsity results are true for k -ply ball arrangements [25] in which each point of space is covered by at most k balls; here k = 2. Our proof follows an approach used by Teng [28] for a related but different family of geometric graphs. Theorem 4.1. For any fixed d, we can test the bipartiteness of an intersection graph of bal ls, and return either a two-coloring of the intersection graph or an odd cycle, in time O(n log n).

Proof. We modify the algorithm of Lemma 4.2, checking Lemma 4.1. Let B be a col lection of n bal ls in Rd hav- the size of each separator produced at each stage of the ing a bipartite intersection graph GB . Then |E (GB )|  algorithm. If, at each stage, the separator size is within cd n for some constant cd  5d/2 2. the bounds expected for a 2-ply neighborhood system, the algorithm will produce an intersection graph of size Proof. Let b0 be the smallest ball in B , with volume O(n) which we can safely test for bipartiteness using a V , and let N (b0 ) denote the set of balls intersecting linear time graph algorithm. b0 . N (b0 ) consists of disjoint balls, else the intersection If, however, some stage produces a separator that is graph would contain a triangle, violating bipartiteness. too large, we terminate the intersection graph construcLet b denote the ball concentric with b0 and having tion algorithm early without constructing the whole  radius 5 times that of b0 . Then, for any ball bi  graph. The separator algorithm is based on transN (b0 ), the volume of bi  b is at least V /2: the volume of forming the input to a ball arrangement on a (d + 1)the intersection is minimized when bi and b0 have equal dimensional sphere, and will only produce a large sepradii and are tangent (Figure 2), in which case b crosses arator in the case that the transformed input has high bi on the equator of bi . The sets bi  b are disjoint, so average density. In this case, we can use the same their volumes add up at most to the overall volume of cutting technique used (in a dual space) in the algob . Thus, if there are i neighbors, iV /2  5d/2 V and rithm of Lemma 4.2 to find a point of high density; that i  5d/2 2. By induction, the intersection graph of all is, a point covered by three or more balls. Any three balls except b0 has at most 5d/2 2(n-1) edges, so (adding balls covering the same point correspond to a triangle the i edges incident to b0 ) the intersection graph of all in the intersection graph. 2 balls has at most 5d/2 2n edges. 2 It seems likely that a similar approach would work The same proof technique leads to a bound of for more general classes of fat ob jects in Rd . We note 5d/2 2k n for the number of intersections in a k -ply neigh- that this O(n log n) time bound significantly improves borhood system, slightly improving a 3d k n bound of the bound of the generic algorithm for connectivity or Miller et al. [25, Theorem 3.3.1]. The other ingredi- bipartiteness. For balls in R2 , the connected compoent we need is an algorithm for constructing intersec- nents may be found in time O(n log n) by using the tion graphs of k -ply neighborhood systems, which uses power diagram of the balls. But, as we now show, we an -cutting technique to find small separators for a can not hope to find a similarly fast bound for connecseparator-based divide and conquer. tivity of balls in higher dimensions, unless we improve on other more well-studied problems. Lemma 4.2. (Eppstein et al. [11]) For any fixed d, the intersection graph of a k -ply neighborhood system in Theorem 4.2. The best possible randomized expected Rd can be constructed in time O(k n + n log n). time bounds for connectivity of unit bal ls in Rd and

863


Euclidean minimum spanning trees in Rd are within and these segments can be ordered by the y -coordinates constant factors of each other. of the crossing points. This crossing sequence changes combinatorially only when the sweep line crosses an Proof. In one direction, a spanning forest of the inter- endpoint of a segment or a crossing point of two section graph of unit balls can be found as a subforest of segments. We define a bund le to be a maximal set of the Euclidean minimum spanning tree of the ball cen- segments, appearing contiguously within the crossing ters. sequence, and all belonging to the same connected In the other direction, suppose we have an algo- component of the truncated arrangement. Thus, the rithm that in time T (n) can find the connected com- bundles form a partition of the crossing sequence into ponents of the intersection graph of a collection of n contiguous subsequences. Note that a single component unit balls. Then we can test whether, in a set of n red of the truncated arrangement may have several or no and blue points, there exists a red-blue pair at distance bundles associated with it. closer than two: compute the connected components of Our algorithm will maintain the following data balls centered at the points and test whether any com- structures: ponent contains points of both colors. A randomized reduction of Chan [4] transforms this decision algorithm · An event queue, containing potential events deinto an optimization algorithm with the same complextailed later. This is a priority queue data structure, ity, for finding the closest red-blue pair, and it is known allowing insertions and deletions of arbitrary obthat this bichromatic closest pair problem and the Eujects, where each ob ject is associated with a point clidean minimum spanning tree problem have asympin the plane and is prioritized lexicographically by totically equal complexities [1, 3, 23]. 2 the coordinates of that point. Possibly a similar deterministic reduction could be found, at the expense of some logarithmic factors, using parametric search, but this would depend on the details of the supposed connected components algorithm. · A spanning forest of the intersection graph of the truncated arrangement. We root the trees in the forest arbitrarily, and consider the input line segments to be colored implicitly, according to the parity of the heights of the corresponding spanning forest vertices. We represent this forest using a data structure that allows vertex insertions, edge insertions (between vertices in different trees, keeping the root of one of the trees), and lookups of the parity of a query vertex.

5 Sweep for segments Next, we describe an efficient algorithm for our original motivating problem: bipartiteness of intersection graphs of line segments. The generic algorithm for this case seems to involve complex ray shooting data structures and does not approach linear time. Instead, we de· For each component of the truncated arrangement, scribe an alternative approach based on the plane sweep two binary search trees, called color trees, one for paradigm. each color of line segment in the component. The Our algorithm sweeps a vertical line left to right ordering of nodes in each tree represents the subacross the arrangement. We define the truncated arsequence of the crossing sequence consisting of the rangement to be the arrangement of line segments segments of that color that belong to that compoformed by intersecting each input line segment with the nent. The data structure used to represent color halfplane to the left of the sweep line. As the algotrees must allow split and concatenate operations rithm progresses, we maintain various data structures, as well as the usual insertion and deletion operadetailed below, to help it keep track of the connected tions. components of the intersection graph of the truncated · Another binary search tree, called the bund le tree, arrangement, and of a two-coloring of each component. representing the bundles of the crossing sequence. Also, as with most plane sweep algorithms, we use a priEach bundle tree node (representing a single bunority queue to maintain a set of potential events at which dle) stores pointers to the topmost and bottommost the other structures being maintained by the algorithm line segments of each color in the bundle, as well as change combinatorially. Each event is associated with a to the color trees of its component. point in the plane, and the x coordinate of this point is used as the event's priority, so that the priority queue We store the following potential events in our event ordering corresponds to the order in which the sweep queue: line crosses the corresponding points. At any point in the algorithm, the sweep line will · A segment insertion event is associated with the cross a subset of segments from the input arrangement, left endpoint of each line segment in our input. If

864


both coordinates have the same x coordinate, the one with smaller y coordinate is considered to be the left endpoint. · A segment deletion event is associated with the right endpoint of each line segment in our input. · Component merge events are associated with pairs of adjacent bundles in the node ordering of the bundle tree. The point associated with this event is the point where the lines through a bottom segment of the top bundle and a top segment of the bottom bundle intersect; each pair of bundles may have up to four such events. If this point is to the left of the sweep line, the component merge event is omitted from the event queue. · An odd cycle event may be associated with each pair of adjacent segments in the node ordering of some color tree. The point associated with this event is the point where the lines through the two segments meet. If this point is to the left of the sweep line, the odd cycle event is omitted from the event queue. Our algorithm, then, repeatedly removes the first event from the event queue, and processes it. Processing an event consists of the following events. · To process a segment insertion event, we create a new tree in the spanning forest, consisting of a single node representing the new segment. We create a color tree for this segment, and create a new bundle tree node for it. We then search the bundle tree for the placement of this segment among the other bundles. If the new bundle should be placed between two bundles, we simply insert it into the bundle tree, remove from the priority queue any component merge event between its two neighbors, and add component merge events from it to its neighbors. If the new bundle's placement is inside an existing bundle, we split that bundle into two bundles, using the color trees to find the new topmost and bottommost segments of each color for each of the two split parts, and then insert the new bundle between the two split parts in the bundle tree. In this latter case, we update the existing component merge events in the event queue to reflect the change in bundle identities, and add new component merge events between the newly created bundle and the two split parts.

and bottom edges of the bundle and update the bundle's component merge events appropriately. If the segment being deleted is the only one in its bundle, we remove that bundle from the bundle tree, along with its associated component merge events; then, if its two neighbors belong to different components of the truncated arrangement, we add a new component merge event between them, or otherwise we merge two adjacent bundles from the same component into a single larger bundle. · To process a component merge event, we add an edge connecting the two crossing segments to the spanning forest of the intersection graph of the truncated arrangement. We do a parity lookup in the spanning forest to determine which two pairs of color trees must be merged. All bundles of one of the two merged components must be nested between two consecutive bundles of the other component, so the color trees for the two components can be merged by splitting the trees for the outer component followed by a pair of concatenations per merged color tree. The same nesting argument shows that at most two pairs of adjacent bundles must merge, which we perform with the appropriate adjustments to the bundle tree and to the set of component merge events in the event queue. · To process an odd cycle event, we form an odd cycle in the intersection graph from an edge between the vertices corresponding to the two crossing segments, together with a path connecting the same two vertices in the spanning forest of the truncated arrangement's intersection graph. We report this odd cycle and terminate the algorithm. Theorem 5.1. We can test the bipartiteness of an intersection graph of n line segments in the plane, and return either a two-coloring of the intersection graph or an odd cycle, in time O(n log n).

Proof. It is not hard to show that each step of the algorithm described above maintains the invariants of each of the data structures, so that when the algorithm terminates it does so either with an odd cycle or with a two-coloring of the arrangement. There are n segment insertion events, n segment deletion events, at most n - 1 component merge events (since each one adds an edge to the spanning forest) and at most one odd cycle event. Each processed event makes a constant · To process a segment deletion event, if the segment number of changes to the data structures, and each data being deleted belongs to a bundle of two or more structure change can be performed in O(log n) time, so segments, we use the color trees to update the top the total time for the algorithm is O(n log n). 2

865


When the segments are found to be bipartite, the algorithm correctly identifies the connected components of their intersection graph. However, it is not able to perform the same connectivity analysis for nonbipartite segment arrangements. The same approach works as well for more general classes of ob jects in the plane. Theorem 5.2. We can test the bipartiteness of an intersection graph of a col lection of simple polygons in the plane, having a total of n sides, and return either a two-coloring of the intersection graph or an odd cycle, in time O(n log n). Proof. We use a similar plane sweep approach and data structures, with some modifications. First, the truncated arrangement now refers to the set of polygons formed by intersecting the input polygons with the halfplane left of the sweep line. A single polygon may be represented as multiple polygons in the truncated arrangement, allowing us to preserve the nesting property used in the algorithm. Second, the crossing sequence, and therefore also the color trees, may include the same polygon more than once. For each appearance of a polygon in a color tree, we maintain the identities of the two polygon edges crossed by the sweep line, so that we can still perform binary searches in the color trees in constant time per step. Third, we have a larger set of possible events. Each polygon vertex causes an event, and these vertices may be classified according to how many incident edges go leftwards or rightwards from the vertex, and (in the case that both go leftwards or both go rightwards) whether the vertex is convex or reflex. There are five possibilities:

arrangement, we merge those components into a single one similarly to our treatment of a component merge event. · A vertex with one leftward and one rightward edge does not change the bundle tree or the crossing sequence, but it does change the identity of the edge crossed by the sweep line, and we make the appropriate change to the corresponding color tree node. · A reflex vertex with two leftward edges corresponds to the split of one item into two items in the crossing sequence, and we split one node in two in the appropriate color tree. · A convex vertex with two leftward edges corresponds to a deletion event in the line segment algorithm, and is handled similarly. As before, there are O(n) events processed, each of which involves a constant number of data structure operations, so the total time is O(n log n). 2

We observe that Hopcroft's problem, testing the existence of a point-line incidence in a set of n points and n lines, can easily be reduced to the problem of finding the connected components of a line segment intersection graph: simply view each point as a line segment with length zero (or a sufficiently small positive length), view each line as a sufficiently long line segment (having endpoints outside the convex hull of the points), and test whether any point belongs to a nontrivial component of the intersection graph. Hopcroft's problem has known · A convex vertex with two rightward edges corre(n4/3 ) lower bounds, in natural and general models sponds to an insertion event in the line segment of geometric computation [12]. Therefore, it seems unalgorithm, and is handled similarly. However, it is likely that an algorithm with a near-linear time bound possible that the vertex occurs within the interior of similar to that for bipartiteness can exist for the conanother polygon; we can detect this situation by lonectivity problem. cating the vertex in the bundle tree and then in the appropriate color trees, and add the newly formed 6 More than two colors truncated polygon to an existing component of the truncated arrangement instead of creating a new Bipartiteness (two-coloring) of geometric intersection component for it. If the vertex occurs within two graphs can obviously be tested in polynomial time, polygons of opposite colors in the same component, and we have described efficient algorithms for several its polygon and the two others form a triangle in important cases of intersection graphs including the line segment intersection graphs arising from the problem of the intersection graph, and we halt immediately. computing the geometric thickness of a drawing. What · A reflex vertex with two rightward edges corre- about coloring with more than two colors? For graphs, sponds to the merger of two polygons in the trun- this is NP-complete, so it is unsurprising that the same cated arrangement into a single polygon. We merge is true for geometric intersection graphs. We outline a the two corresponding nodes in the appropriate proof for planar unit disks and for line segments; the color tree. If the two polygons previously belonged result for unit disks was previously known [6, 14] but for to different connected components of the truncated completeness we repeat it here.

866


Figure 3: NP-completeness reductions from degree-four planar graph 3-coloring to line segment 3-coloring (top) and to unit disk 3-coloring (bottom). Theorem 6.1. It is NP-complete to test 3-colorability There are several potential directions for future reof an intersection graph of line segments in the plane, search. Can the generic bipartiteness algorithm be imor of unit disks in the plane. proved upon for ob jects that are not fat and nonplanar, such as rectangular boxes or triangles in R3 ? Might Proof. We use a reduction from 3-colorability of planar the chromatic number of a geometric intersection graph graphs with degree at most four [13]. For line segments, be easier to approximate than it is for general graphs? we find a straight-line embedding of the graph on a For general graphs, bipartiteness can be maintained efpolynomial size grid [26], replace each vertex by a short ficiently in a dynamic setting [10, 18]; can bipartiteline segment, and replace each edge by a gadget formed ness of intersection graphs be maintained efficiently dyby three mutually crossing line segments (Figure 3, top). namically or kinetically? Finally, for which other useFor unit disks, we find an orthogonal drawing of the ful graph properties is it possible to provide similar graph on a grid, so that its edges are drawn with bends speedups in the geometric setting over a naive approach along grid edges [7, 27]. We scale the grid so that its edge that constructs the entire intersection graph? lengths are a suitable constant times the unit radius of the disks, replace each vertex of the drawing by a Acknowledgements single disk, and replace each edge by a chain of disks meeting in triples (Figure 3, bottom). The details are This work was supported in part by NSF grant CCRstraightforward, and we omit them. 2 9912338. 7 Conclusions We have investigated several algorithms for testing bipartiteness of intersection graphs, one for arbitrary geometric ob jects, based only on the existence of a decremental intersection detection data structure, and two faster ones for fat ob jects (balls in Rd ) and planar objects (line segments or simple polygons). We have also investigated the relation between bipartiteness testing and connectivity, and provided evidence that, for some types of geometric ob ject, connected component analysis is strictly more difficult than bipartiteness testing. References
[1] P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computatational Geometry 6:407­422, 1991. [2] P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, pp. 1­56. AMS, Contemporary Mathematics 223, 1999, http: //compgeom.cs.uiuc.edu/jeffe/pubs/survey.html. [3] P. B. Callahan. The Wel l-Separated Pair Decomposition and its Applications. Ph.D. thesis,

867


Johns Hopkins Univ., 1995. [4] T. M.-Y. Chan. Geometric applications of a randomized optimization technique. Discrete & Computatational Geometry 22(4):547­567, December 1999. [5] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM 39(1):1­54, 1992. [6] B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Mathematics 86:165­177, 1990. [7] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999. [8] M. B. Dillencourt, D. Eppstein, and D. S. Hirschberg. Geometric thickness of complete graphs. J. Graph Algorithms & Applications 4(3):5­17, 2000, arXiv:math.CO/9910185. [9] D. Eppstein. Separating thickness from geometric thickness. Proc. 10th Int. Symp. Graph Drawing (GD'02), pp. 150­161. Springer-Verlag, Lecture Notes in Computer Science 2528, 2002, arXiv:math.CO/0204252. [10] D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification -- A technique for speeding up dynamic graph algorithms. J. ACM 44(5):669­696, September 1997. [11] D. Eppstein, G. L. Miller, and S.-H. Teng. A deterministic linear time algorithm for geometric separators and its applications. Fundamenta Informaticae 22(4):309­331, April 1995. [12] J. Erickson. New lower bounds for Hopcroft's problem. Discrete & Computatational Geometry 16(4):389­418, 1996, http: //compgeom.cs.uiuc.edu/jeffe/pubs/hopcroft.html. [13] M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science 1:237­267, 1976. [14] A. Graf, M. Stumpf, and G. Weißenfels. On coloring unit disk graphs. Algorithmica 20(3):277­293, 1998. [15] L. J. Guibas, J. E. Hershberger, S. Suri, and L. Zhang. Kinetic connectivity of unit disks. Discrete & Computatational Geometry 25(4):591­610, April 2001. [16] J. E. Hershberger and S. Suri. Kinetic connectivity of rectangles. Proc. 15th Symp. Computational Geometry, pp. 237­246. ACM, June 1999. [17] J. E. Hershberger and S. Suri. Simplified kinetic connectivity for rectangles and hypercubes. Proc. 12th Symp. Discrete Algorithms (SODA'01), pp. 158­167. ACM and SIAM, January 2001. [18] J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic graph algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4):723­760, July 2001. [19] J. P. Hutchinson, T. Shermer, and A. Vince. On representation of some thickness-two graphs. Proc. 3rd Int. Symp. Graph Drawing (GD'95), pp. 324­332. Springer-Verlag, Lecture Notes in Computer Science

1027, September 1995. [20] H. Imai. Finding connected components of an intersection graph of squares in the Euclidean plane. Inform. Proc. Lett. 15(3):125­128, 1982. [21] H. Imai and T. Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4:310­323, 1983. [22] P. C. Kainen. Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg 39:88­95, 1973. [23] D. Krznaric and C. Levcopoulos. Minimum spanning trees in d dimensions. Proc. 5th Eur. Symp. Algorithms, pp. 341­349. Springer-Verlag, Lecture Notes in Computer Science 1248, September 1997. [24] A. Mansfield. Determining the thickness of a graph is NP-hard. Math. Proc. Cambridge Philos. Soc. 93(9):9­23, 1983. [25] G. L. Miller, S.-H. Teng, W. P. Thurston, and S. A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM 44(1):1­29, January 1997. [26] W. Schnyder. Embedding planar graphs on the grid. Proc. 1st Symp. Discrete Algorithms, pp. 138­148. ACM and SIAM, January 1990. [27] R. Tamassia and I. G. Tollis. Tesselation representations of planar graphs. Proc. 27th Al lerton Conf. Commun. Control Comput., pp. 48­57, 1989. [28] S.-H. Teng. Points, spheres, and separators: a unified approach to graph partitioning. Ph.D. thesis, Carnegie-Mellon Univ., School of Computer Science, 1991. [29] D. R. Wood. Geometric thickness in a grid of linear area. Proc. Euroconf. Combinatorics, Graph Theory, and Applications, pp. 310­315. Univ. Aut`noma de o Barcelona, Centre de Recerca Matem`tica, September a 2001, http://www.cs.usyd.edu.au/davidw/papers/ Wood- COMB01.ps.

868