On the Construction of Planar Embedding for a Class of Orthogonal Polyhedra

被引：0

作者：

Karmakar, Nilanjana ^{[1
]}

Biswas, Arindam ^{[2
]}

Nandy, Subhas C. ^{[3
]}

Bhattacharya, Bhargab B. ^{[4
]}

机构：

[1] St Thomas Coll Engn & Technol, Dept Informat Technol, Kolkata, India

[2] Indian Inst Engn Sci & Technol, Dept Informat Technol, Sibpur, India

[3] Indian Stat Inst, Adv Comp & Microelect Unit, Kolkata, India

[4] Indian Inst Technol Kharagpur, Dept Comp Sci & Engn, Kharagpur, W Bengal, India

来源：

COMBINATORIAL IMAGE ANALYSIS, IWCIA 2022 | 2023年 / 13348卷

关键词：

Orthogonal polyhedron; Planar graph; Graph drawing; GRAPHS; ALGORITHM; THEOREM;

D O I：

10.1007/978-3-031-23612-9_6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

2D-representations of 3D digital objects find versatile applications to computer vision, robotics, medical imaging, and in discrete geometry. This work presents an algorithm for constructing a planar embedding with only straight-line edges for a general non-intersecting orthogonal polyhedron that has genus 0. We discover certain characterizations of vertices and edges of a polyhedron that lead to efficient graph-drawing on the 2D plane. The original orthogonal polyhedron can be fully reconstructed from this graph provided the information regarding the coordinates of vertices, are preserved. The time complexity of the proposed embedding is linear in the number of edges of the orthogonal polyhedron.

引用

页码：84 / 104

页数：21

共 50 条

[11] Planar graphs producing no strongly almost trivial embedding
Huh, Y
Oh, S
JOURNAL OF GRAPH THEORY, 2003, 43 (04) : 319 - 326
[12] Construction of Orthogonal Nearly Latin Hypercubes
Steinberg, David M.
Lin, Dennis
QUALITY AND RELIABILITY ENGINEERING INTERNATIONAL, 2015, 31 (08) : 1397 - 1406
[13] Construction of Orthogonal CC-sets
Brodnik, Andrej
Palangetic, Marko
Siladi, Daniel
Jovicic, Vladan
INFORMATICA-AN INTERNATIONAL JOURNAL OF COMPUTING AND INFORMATICS, 2019, 43 (01): : 19 - 22
[14] On embedding an outer-planar graph in a point set
Bose, P
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2002, 23 (03): : 303 - 312
[15] Non-positive curvature and the planar embedding conjecture
Sidiropoulos, Anastasios
2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 177 - 186
[16] Simultaneous Embedding of a Planar Graph and Its Dual on the Grid
Cesim Erten
Stephen G. Kobourov
Theory of Computing Systems, 2005, 38 : 313 - 327
[17] Simultaneous embedding of a planar graph and its dual on the grid
Erten, C
Kobourov, SG
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2002, 2518 : 575 - 587
[18] Hat guessing number for the class of planar graphs is at least 22
Latyshev, Aleksei
Kokhas, Konstantin
DISCRETE MATHEMATICS, 2024, 347 (03)
[19] The Construction of 4-Regular Polyhedra Containing Triangles, Quadrilaterals and Pentagons
Yao, Haiyuan
Hu, Guang
Zhang, Heping
Qiu, Wen-Yuan
MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2010, 64 (02) : 345 - 358
[20] A Lower Bound on the Distortion of Embedding Planar Metrics into Euclidean Space
Ilan Newman
Yuri Rabinovich
Discrete & Computational Geometry, 2002, 29 : 77 - 81

← 1 2 3 4 5 →