بررسي رسم متعامد سه بعدي با نماي داده شده در چند كلاس مختلف از گراف ها

On the 3D-Orthogonal Drawing with Given Shapes in Some Classes of Graphs

An orthogonal drawing of a graph is a drawing where every vertex has an integer coordinate and every edge is a chain of segments that are parallel to the axis. An orthogonal shape of a graph is a labeling of the edges of the graph with the labels north, south, east, west, up and down that represents the direction of edges. Given an orthogonal shape of a graph, the problem of determining whether there exists a drawing with this shape, is NP-hard. There are linear time algorithms for some classes of graphs. In this paper, the previous results are stated, and then linear time algorithms are presented for solving the problem for shapes of trees and unicyclic graphs. In addition, a sufficient condition for shape of k -path graphs is stated.