|
|
uniqueness of rectangularly dualizable graphs
|
|
|
|
|
نویسنده
|
kumar vinod ,shekhawat krishnendra
|
منبع
|
communications in combinatorics and optimization - 2024 - دوره : 9 - شماره : 1 - صفحه:13 -25
|
چکیده
|
A generic rectangular partition is a partition of a rectangle into a finite number of rectangles provided that no four of them meet at a point. a graph h is called dual of a plane graph g if there is one−to−one correspondence between the vertices of g and the regions of h, and two vertices of g are adjacent if and only if the corresponding regions of h are adjacent. a plane graph is a rectangularly dualizable graph if its dual can be embedded as a rectangular partition. a rectangular dual r of a plane graph g is a partition of a rectangle into n−rectangles such that (i) no four rectangles of r meet at a point, (ii) rectangles in r are mapped to vertices of g, and (iii) two rectangles in r share a common boundary segment if and only if the corresponding vertices are adjacent in g. in this paper, we derive a necessary and sufficient for a rectangularly dualizable graph g to admit a unique rectangular dual upto combinatorial equivalence. further we show that g always admits a slicible as well as an area−universal rectangular dual.
|
کلیدواژه
|
plane graphs ,rectangularly dualizable graphs ,rectangular duals ,rectangular partitions
|
آدرس
|
birla institute of technology & science; pilani campus, department of mathematics, india, birla institute of technology & science; pilani campus, department of mathematics, india
|
پست الکترونیکی
|
krishnendra.shekhawat@pilani.bits-pilani.ac.in
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|