Alternative Proof of Linear Tangle and Linear Obstacle: An Equivalence Result

Takaaki Fujita *

Graduate school of Science and Technology, Gunma University, 1-5-1 Tenjin-cho Kiryu Gunma 376-8515, Japan.

*Author to whom correspondence should be addressed.


Linear-width is a widely recognized and highly valued graph width parameter. The concepts of linear tangle and linear obstacle are dual concepts of linear-width. In this concise paper, we present an alternative proof of the equivalence between linear tangle and linear obstacle.

Keywords: Linear width, linear tangle, linear obstacle, connectivity system

How to Cite

Fujita , T. (2023). Alternative Proof of Linear Tangle and Linear Obstacle: An Equivalence Result. Asian Research Journal of Mathematics, 19(8), 61–66.


Download data is not yet available.


Yamazaki, Koichi. Tangle and maximal ideal." WALCOM: Algorithms and Computation: 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017, Proceedings 11. Springer International Publishing; 2017.

Fluck, E. Tangles and Hierarchical Clustering. arXiv preprint arXiv:2203.08731; 2022.

Fedor V Fomin, Dimitrios M Thilikos. On the monotonicity of games generated by symmetric submodular functions. Discrete Applied Mathematics. 2003;131(2):323–335.

Jim Geelen, Bert Gerards, Neil Robertson, Geoff Whittle. Obstructions to branch-decomposition of matroids. Journal of Combinatorial Theory, Series B. 2006;96(4):560–570.

Koutsonas, Athanassios, Dimitrios M. Thilikos, and Koichi Yamazaki. Outerplanar obstructions for matroid pathwidth. Discrete Mathematics. 2014;315:95-101.

Paul, Christophe, Evangelos Protopapas, Dimitrios M. Thilikos. Graph parameters, universal obstructions, and WQO. arXiv preprint arXiv:2304.03688; 2023.

Reed, Bruce A. Tree width and tangles: A new connectivity measure and some applications. Surveys in combinatorics. 1997;87-162.

Diestel Reinhard. Ends and tangles. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. BerlinHeidelberg: Springer Berlin Heidelberg. 2017;87(2).

Fujita T. Revisiting Linear Width: Rethinking the Relationship Between Single Ideal and Linear Obstacle. arXiv preprint arXiv:2305.04740; 2023.

Fomin, Fedor V, Tuukka Korhonen. Fast fpt-approximation of branchwidth. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing; 2022.

Kanté, Mamadou Moustapha, et al. Obstructions for matroids of path-width at most k and Graphs of linear rank-width at most k. Journal of Combinatorial Theory, Series B. 2023;160:15-35.

Kobayashi, Yasuaki, Yu Nakahata. A note on exponential-time algorithms for linearwidth. arXiv preprint arXiv:2010.02388; 2020.

Fujita T. Reconsideration of tangle and ultrafilter using separation and partition. arXiv preprint arXiv:2305.04306; 2023.

Bumpus Benjamin Merlin, Meeks Kitty, Pettersson William. Directed branch-width: A directed analogue of tree-width. arXiv preprint arXiv:2009.08903; 2020.

Bożyk Łukasz, et al. On objects dual to tree-cut decompositions. Journal of Combinatorial Theory, Series B. 2022;157:401-428.

Takaaki Fujita, Koichi Yamazaki. Linear-width and single ideal. The 20th Anniversary of the Japan Conference on Discrete and Computational Geometry, Graphs, and Games. 2017;110‒111.

Fujita T, Yamazaki K. Equivalence between Linear Tangle and Single Ideal. Open Journal of Discrete Mathematics. 2019;9:7-10.

DOI: 10.4236ojdm.2019.91002

Daniel Bienstock. Graph searching, path-width, tree-width and related problems (a survey). Reliability of Computer and Communication Networks , Vol.DIMACS. Series in Discrete Mathematics and Theoretical Computer Science. 1989;33‒50.

Fujita, Takaaki, and Koichi Yamazaki. Tangle and ultrafilter: Game theoretical interpretation. Graphs and Combinatorics. 2020;36(2):319-330.

Seymour P, Thomas R. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B. 1993;58(1):22–23.

Isolde Adler. Games for width parameters and monotonicity. arXiv preprint arXiv:0906.3857; 2009.

Schlechta, Karl. Non-monotonic logic: preferential versus algebraic semantics. David Makinson on Classical Methods for Non-Classical Problems. 2014;167-193.

Dov Gabbay, Karl Schlechta. Conditionals and modularity in general logics; 2010.