NDLI: Efficient Algorithms for Geometric Graph Search Problems

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Asano, Takao Imai, Hiroshi
Copyright Year	1986
Abstract	In this paper, we show that many graph search problems can be solved quite efficiently for a geometric intersection graph of horizontal and vertical line segments. We first extract several basic operations for depth first search and breadth first search on a graph. Then we present data structures for the intersection graph in terms of which those operations can be implemented in an efficient manner. The data structures enable us to solve various graph search problems besides depth first search and breadth first search. Specifying the results obtained in this paper for an intersection graph of n horizontal and vertical segments with m pairs of intersecting segments, we obtain algorithms with the following complexity, where $N = \min \{ m,n\log n\} $. (i) Depth first search and breadth first search can be executed in $O(n\log n)$ time and $O(N)$ space. (ii) The biconnected components can be found in $O(n\log n)$ time and $O(N)$ space. (iii) A maximum matching and a maximum independent set can be found in $O(\sqrt n N)$ time and $O(N)$ space when no two horizontal (vertical) segments intersect. (iv) The connectivity $k_G $ can be found in $O(k_G n^{{3 / 2}} N)$ time and $O(N)$ space. Our algorithms can be applied to various practical problems such as the problem of finding a minimum dissection of a rectilinear region, which arises in the manipulation of VLSI artwork data, and the problem of determining whether there is a Manhattan wiring on a single layer, which arises in the design automation of digital systems.
Starting Page	478
Ending Page	494
Page Count	17
File Format	PDF
ISSN	00975397
DOI	10.1137/0215033
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	15
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-13
Access Restriction	Subscribed
Subject Keyword	depth-first search orthogonal segment intersection search computational geometry segment tree linear-time set union algorithm intersection graph graph algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Depth-First Search and Linear Graph Algorithms

Local and Union Boxicity

Finding Dominators in Directed Graphs

Novel transformation techniques using q-heaps with applications to computational geometry

Computing the Geometric Intersection Number of Curves

Depth first search and linear graph algorithms (1972)

Efficient parallel algorithms for chordal graphs (1989)

Instance-Optimal Geometric Algorithms

Recognizing unordered depth-first search trees of an undirected graph in parallel.

Efficient Algorithms for Geometric Graph Search Problems

Similar Documents

Depth-First Search and Linear Graph Algorithms

Local and Union Boxicity

Finding Dominators in Directed Graphs

Novel transformation techniques using q-heaps with applications to computational geometry

Computing the Geometric Intersection Number of Curves

Depth first search and linear graph algorithms (1972)

Efficient parallel algorithms for chordal graphs (1989)

Instance-Optimal Geometric Algorithms

Recognizing unordered depth-first search trees of an undirected graph in parallel.

Efficient Algorithms for Geometric Graph Search Problems