NDLI: On the Optimal Layout of Planar Graphs with Fixed Boundary

Please wait, while we are loading the content...

On the Optimal Layout of Planar Graphs with Fixed Boundary

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Becker, B. Hotz, G.
Copyright Year	1987
Abstract	The optimal planar layout of planar graphs with respect to the $L_1 $- or $L_2 $-metric leads to NP-hard problems, if one assumes the nodes of the graph to be fixed in the plane (see [FiPa], [Be]).In this paper we consider the (optimal) layout of graphs with fixed boundary (i.e., graphs, where only the nodes of a given cycle of the graph have fixed positions in the plane). The investigated layouts are straight line embeddings in a continuous part of the plane; the cost of a layout is calculated with help of very general cost functions including the pth power of the usual Euclidean distance metric for $p = 2,3, \cdots $ (for short, $l_p $-metric).For a large class of graphs, which, for example, occur in chip layout problems as the abstract structure of switching circuits, we show the existence and uniqueness of the optimal layout.The main part of the paper is concerned with planar graphs. We get an interesting characterization of nonplanar layouts of planar graphs, which shows that the optimal layout of a planar graph is planar or at least quasiplanar. This property makes it possible to decompose the general layout problem into two independent problems: (i) Find a layout of a circuit that is not necessarily planar, but that has an lallowed crossing behaviour. (ii) Fix the crossing points and then optimize the layout. Our theorems show that no new contacts (crossing points) will be generated.In the Appendix we outline some (efficient, polynomial time) methods for the construction of optimal layouts and give as an example the optimal layouts of a recursively defined n-bit adder and multiplier.
Starting Page	946
Ending Page	972
Page Count	27
File Format	PDF
ISSN	00975397
DOI	10.1137/0216061
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	5
Volume Number	16
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-31
Access Restriction	Subscribed
Subject Keyword	Planar graphs; geometric and topological aspects of graph theory star $l_p $-metric convex point (quasi) planar graph with fixed boundary (optimal) layout Relations with graph theory
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

On the Queue Number of Planar Graphs

Noncrossing Subgraphs in Topological Layouts

Nonconvex Representations of Plane Graphs

How to Morph Planar Graph Drawings

The Number of Edges in $k$-Quasi-planar Graphs

Multiple-Source Shortest Paths in Embedded Graphs

On planarity of compact, locally connected, metric spaces

Star Coloring and Acyclic Coloring of Locally Planar Graphs

Finding Cycles with Topological Properties in Embedded Graphs

On the Optimal Layout of Planar Graphs with Fixed Boundary

Similar Documents

On the Queue Number of Planar Graphs

Noncrossing Subgraphs in Topological Layouts

Nonconvex Representations of Plane Graphs

How to Morph Planar Graph Drawings

The Number of Edges in $k$-Quasi-planar Graphs

Multiple-Source Shortest Paths in Embedded Graphs

On planarity of compact, locally connected, metric spaces

Star Coloring and Acyclic Coloring of Locally Planar Graphs

Finding Cycles with Topological Properties in Embedded Graphs

On the Optimal Layout of Planar Graphs with Fixed Boundary