iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S00224-008-9117-Y
Drawing Borders Efficiently | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

Drawing Borders Efficiently

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

A spreadsheet, especially MS Excel, is probably one of the most popular software applications for personal-computer users and gives us convenient and user-friendly tools for drawing tables. Using spreadsheets, we often wish to draw several vertical and horizontal black lines on selective gridlines to enhance the readability of our spreadsheet. Such situations we frequently encounter are formulated as the Border Drawing Problem (BDP). Given a layout of black line segments, we study how to draw it efficiently from an algorithmic view point, by using a set of border styles and investigate its complexity. (i) We first define a formal model based on MS Excel, under which the drawability and the efficiency of border styles are discussed, and then (ii) show that unfortunately the problem is \(\mathcal{NP}\) -hard for the set of the Excel border styles and for any reasonable subset of the styles. Moreover, in order to provide potentially more efficient drawing, (iii) we propose a new compact set of border styles and show a necessary and sufficient condition of its drawability.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berman, P., DasGupta, B.: Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica 17(4), 331–356 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  2. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976)

    MATH  MathSciNet  Google Scholar 

  3. Culberson, J.C., Reckhow, R.A.: Covering polygons is hard. J. Algorithms 17, 2–44 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  4. Edmonds, J., Gryz, J., Liang, D., Miller, R.J.: Mining for empty rectangles in large data sets. Theor. Comput. Sci. 296, 435–452 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  5. Garey, M.R., Johnson, D.S.: Computers and Intractability—A Guide to the Theory of \(\mathcal{NP}\) -Completeness. Freeman, New York (1979)

    Google Scholar 

  6. Greenberg, D.S., Istrail, S.C.: Physical mapping by STS hybridization: algorithmic strategies and the challenge of software evaluation. J. Comput. Biol. 2, 219–274 (1995)

    Article  Google Scholar 

  7. Gudmundsson, J., Levcopoulos, C.: Close approximations of minimum rectangular coverings. J. Comb. Optim. 3(4), 437–452 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  8. Hegedüs, A.: Algorithms for covering polygons by rectangles. Comput. Aided Geom. Des. 14, 257–260 (1982)

    Google Scholar 

  9. Anil Kumar, V.S., Ramesh, H.: Covering rectilinear polygons with axis-parallel rectangles. SIAM J. Comput. 32(6), 1509–1541 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Magwene, P.M., Lizardi, P., Kim, J.: Reconstructing the temporal ordering of biological samples using microarray data. Bioinformatics 19(7), 842–850 (2003)

    Article  Google Scholar 

  11. Masek, W.J.: Some \(\mathcal{NP}\) -complete set covering problems. MIT, Cambridge. Unpublished manuscript (1978). Referenced in [5]

  12. Reuhman, D.: A short route to tgif pictures. ftp://bourbon.usc.edu/pub/tgif/contrib/tgifintro/ (2002)

  13. Suri, S.: Polygons. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (1997)

    Google Scholar 

  14. Xfig User Manual (ver. 3.2.5). http://www.xfig.org/userman/

Download references

Author information

Authors and Affiliations

  1. School of Informatics, Kyoto University, Kyoto, 606-8501, Japan

    Kazuo Iwama

  2. Department of Systems Design and Informatics, Kyushu Institute of Technology, Fukuoka, 820-8502, Japan

    Eiji Miyano

  3. Department of Computer Science and Communication Engineering, Kyushu University, Fukuoka, 819-0395, Japan

    Hirotaka Ono

Authors
  1. Kazuo Iwama
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eiji Miyano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hirotaka Ono
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hirotaka Ono.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Iwama, K., Miyano, E. & Ono, H. Drawing Borders Efficiently. Theory Comput Syst 44, 230–244 (2009). https://doi.org/10.1007/s00224-008-9117-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-008-9117-y

Keywords

Search

Navigation