• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Computing and Combinatorics Conference >No-Bend Orthogonal Drawings and No-Bend Orthogonally Convex Drawings of Planar Graphs (Extended Abstract)
【24h】

No-Bend Orthogonal Drawings and No-Bend Orthogonally Convex Drawings of Planar Graphs (Extended Abstract)

机译：平面图的无弯正交图和无弯正交凸图（扩展摘要）

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A plane graph is a planar graph with a fixed planar embedding in the plane. In an orthogonal drawing of a plane graph each vertex is drawn as a point and each edge is drawn as a sequence of vertical and horizontal line segments. A bend is a point at which the drawing of an edge changes its direction. A necessary and sufficient condition for a plane graph of maximum degree 3 to have a no-bend orthogonal drawing is known which leads to a linear-time algorithm to find such a drawing of a plane graph, if it exists. A planar graph G has a no-bend orthogonal drawing if any of the plane embeddings of G has a no-bend orthogonal drawing. Since a planar graph G of maximum degree 3 may have an exponential number of planar embeddings, determining whether G has a no-bend orthogonal drawing or not using the known algorithm for plane graphs takes exponential time. The best known algorithm takes 0(n ) time for finding a no-bend orthogonal drawing of a biconnected planar graph of maximum degree 3. In this paper we give a linear-time algorithm to determine whether a biconnected planar graph G of maximum degree 3 has a no-bend orthogonal drawing or not and to find such a drawing of G, if it exists. We also give a necessary and sufficient condition for a biconnected planar graph G of maximum degree 3 to have a no-bend 'orthogonally convex' drawing D; where any horizontal and vertical line segment connecting two points in a facial polygon P in D lies totally within P. Our condition leads to a linear-time algorithm for finding such a drawing, if it exists.
机译：平面图是在平面中嵌入固定平面的平面图。在平面图的正交图中，每个顶点绘制为一个点，每个边缘绘制为一系列垂直和水平线段。折弯是边的图形更改其方向的点。已知最大度数为3的平面图具有无弯角正交图的必要和充分条件，这导致了线性时间算法来找到平面图的这种图（如果存在）。如果G的任何平面嵌入都具有无弯角正交图，则平面图G具有无弯角正交图。由于最大度数为3的平面图G可能具有指数数量的平面嵌入，因此使用已知的平面图算法确定G是否具有无弯角正交图会花费指数时间。最著名的算法需要0（n）时间来找到最大度为3的双向连接平面图的无弯正交图。在本文中，我们给出了一种线性时间算法来确定最大度为3的双向连接的平面图G是否具有无弯角正交图，并找到存在的此类G图。我们还为最大度为3的双连通平面图G给出了无弯的“正交凸”图D提供了充要条件。其中连接D中的面部多边形P中的两个点的任何水平和垂直线段都完全位于P内。我们的条件导致找到一种线性时间算法来查找这种图形（如果存在）。

著录项

  • 来源
  • 会议地点 Xian(CN)
  • 作者

    Md. Manzurul Hasan; Md. Saidur Rahman;

  • 作者单位

    Graph Drawing and Information Visualization Laboratory Department of Computer Science and Engineering (CSE) Bangladesh University of Engineering and Technology (BUET) Dhaka Bangladesh Department of Computer Science American International University-Bangladesh (AIUB) Dhaka Bangladesh;

    Graph Drawing and Information Visualization Laboratory Department of Computer Science and Engineering (CSE) Bangladesh University of Engineering and Technology (BUET) Dhaka Bangladesh;

  • 会议组织
  • 原文格式 PDF
  • 正文语种
  • 中图分类
  • 关键词

    Orthogonal drawings; Orthogonally convex drawings; Planar graphs;

    机译：正交图；正交凸图；平面图;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号