A5028026748- Advanced Graph Theory Research
- Computational Geometry and Mesh Generation
- Graph Labeling and Dimension Problems
- Advanced Algebra and Logic
- Complexity and Algorithms in Graphs
- Digital Image Processing Techniques
- graph theory and CDMA systems
- Graph theory and applications
- Interconnection Networks and Systems
Tianjin University
2019-2023
A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only some bar for one can see other via an unobstructed vertical channel positive width. The least such $G$ has is number $G$, denoted by $b(G)$. We show $H$ spanning subgraph then $b(H)\le b(G)+1$. It follows $b(G)\le \lceil n/6\rceil+1$ when $n$-vertex graph. This improves upper bound obtained Chang et al. (SIAM J. Discrete Math. 18 (2004) 462).
Visibility representation of digraphs was introduced by Axenovich, Beveridge, Hutch\-inson, and West (\emph{SIAM J. Discrete Math.} {\bf 27}(3) (2013) 1429--1449) as a natural generalization $t$-bar visibility undirected graphs. A {\it representation} digraph $G$ assigns each vertex at most $t$ horizontal bars in the plane so that there is an arc $xy$ if only some bar for $x$ "sees" $y$ above it along unblocked vertical strip with positive width. The number} $b(G)$ least such has...