Browsing by Author "Poon, Sheung-Hung"

Now showing 1 - 4 of 4

Boundary Labeling with Flexible Label Positions
(2014)
Huang, Zhi-Dong
;
Poon, Sheung-Hung
;
Lin, Chun-Cheng
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Boundary labeling connects each point site in a rectangular map to a label on the sides of the map by a leader, which may be a straight-line segment or a polyline. In the conventional setting, the labels along a side of the map form a single stack of labels in which labels are placed consecutively one by one in a sequence, and the two end sides of a label stack must respect the sides of the map. However, such a setting may be in conflict with generation of a better boundary labeling, measured by the total leader length or the number of bends of leaders. As a result, this paper relaxes this setting to propose the boundary labeling with flexible label positions, in which labels are allowed to be placed at any non-overlapping location along the sides of the map so that they do not necessarily form only one single stack, and the two end sides of label stacks do not need to respect the sides of the map. In this scenario, we investigate the total leader length minimization problem and the total bend minimization problem under several variants, which are parameterized by the number of sides to which labels are attached, their label size, port types, and leader types. It turns out that almost all of the total leader length minimization problems using nonuniform-size labels are NP-complete except for one case, while the others can be solved in polynomial time.
Designing and Annotating Metro Maps with Loop Lines
(2015)
Wu, Hsiang-Yun
;
Poon, Sheung-Hung
;
Takahashi, Shigeo
;
Arikawa, Masatoshi
;
Lin, Chun-Cheng
Schematic metro maps provide an effective means of simplifying the geographical configuration of public rapid transportation systems. Nonetheless, travelers still find it difficult to identify routes of a specific topology on the maps because it is usually hidden behind the conventional octilinear layout of the entire map. In this paper, we present an approach to designing schematic maps with loop lines, which are drawn as circles together with annotation labels for guiding different traveling purposes. Our idea here is to formulate the aesthetic criteria as mathematical constraints in the mixed-integer programming model, which allows us to either align stations on the loop line at a grid if they are interchange stations or non-interchange stations on a circle otherwise. We then distribute the annotation labels associated with stations on the loop line evenly to the four side boundary of the map domain in order to make full use of the annotation space, while maximally avoiding intersections between leader lines and the metro network by employing a flow network algorithm. Finally, we present several experimental results generated by our prototype system to demonstrate the feasibility of the proposed approach.
On Complexity of Total Vertex Cover on Subcubic Graphs
(2017-01-01)
Poon, Sheung-Hung
;
Wang, Wei-Lin
;
資訊工程學系
;
Department of Computer Science
A total vertex cover is a vertex cover whose induced subgraph consists of a set of connected components, each of which contains at least two vertices. A t-total vertex cover is a total vertex cover where each component of its induced subgraph contains at least t vertices. The total vertex cover (TVC) problem and the t-total vertex cover (t-TVC) problem ask for the corresponding cover set with minimum cardinality, respectively. In this paper, we first show that the t-TVC problem is NP-complete for connected subcubic grid graphs of arbitrarily large girth. Next, we show that the t-TVC problem is NP-complete for 3-connected cubic planar graphs. Moreover, we show that the t-TVC problem is APX-complete for connected subcubic graphs of arbitrarily large girth.
One-and-a-Half-Side Boundary Labeling
(2011)
Lin, Chun-Cheng
;
Poon, Sheung-Hung
;
Takahashi, Shigeo
;
Wu, Hsiang-Yun
;
Yen, Hsu-Chun
In boundary labeling, each point site in a rectangular map is connected to a label outside the map by a leader, which may be a rectilinear or a straight-line segment. Among various types of leaders, the so-called type-opo leader consists of three segments (from the site to its associated label) that are orthogonal, then parallel, and then orthogonal to the side to which the label is attached. In this paper, we investigate the so-called 1.5-side boundary labeling, in which, in addition to being connected to the right side of the map directly, type-opo leaders can be routed to the left side temporarily and then finally to the right side. It turns out that allowing type-opo leaders to utilize the left side of a map is beneficial in the sense that it produces a better labeling result; in some cases. To understand this new version of boundary labeling better, we investigate from a computational complexity viewpoint the total leader length minimization problem as well as the bend minimization problem for variants of 1.5-side boundary labeling, which are parameterized by the underlying label size (uniform vs. nonuniform) and port type (fixed-ratio, fixed-position, vs. sliding). For the case of nonuniform labels, the above two problems are intractable in general. We are able to devise pseudopolynomial time solutions for such intractable problems, and also identify the role played by the number of distinct labels in the overall complexity. On the other hand, if labels are identical in size, both problems become solvable in polynomial time. We also characterize the cases for which utilizing the left side for routing type-opo leaders does not help.