Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

DOI10.1016/0196-6774(83)90012-3zbMath0548.68067OpenAlexW2086551550MaRDI QIDQ3340176

Takao Asano, Hiroshi Imai

Publication date: 1983

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(83)90012-3

zbMATH Keywords

algorithmintersection graphcolorabilityNP-completecomponentsmaximum cliquerectanglesrectangular region

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (49)

A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids ⋮ Boxicity and treewidth ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Max point-tolerance graphs ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ Connected component and simple polygon intersection searching ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ On Local Structures of Cubicity 2 Graphs ⋮ Complexity of maximum cut on interval graphs ⋮ Many disjoint edges in topological graphs ⋮ Approximation algorithms for intersection graphs ⋮ Parallel computational geometry of rectangles ⋮ Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking ⋮ Matching colored points with rectangles ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Many disjoint edges in topological graphs ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Cubicity of interval graphs and the claw number ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Computing coverage kernels under restricted settings ⋮ The cubicity of hypercube graphs ⋮ Disjoint edges in complete topological graphs ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ Unnamed Item ⋮ In-place algorithms for computing a largest clique in geometric intersection graphs ⋮ On rectangle intersection graphs with stab number at most two ⋮ Connected component and simple polygon intersection searching ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ An upper bound for cubicity in terms of boxicity ⋮ Label placement by maximum independent set in rectangles ⋮ A note on maximum independent sets in rectangle intersection graphs ⋮ DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION ⋮ ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE ⋮ Facility location problems in the plane based on reverse nearest neighbor queries ⋮ On the stab number of rectangle intersection graphs ⋮ On the cubicity of certain graphs ⋮ Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points ⋮ Fast stabbing of boxes in high dimensions ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity ⋮ Lower bounds for boxicity ⋮ Interval graphs and related topics ⋮ On a circle placement problem

This page was built for publication: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane