<p>I would suggest looking at these survey papers and tracking down the citations in the bibliography, and digging up subsequent papers which cited these. </p>

<ul>
<li><p>Walter Hower, and  Winfried Graf. <em>Research in constraint-based layout, visualization, CAD, and related topics : a bibliographical survey</em>, 1995. </p></li>
<li><p>Simon Lok and Steven Feiner, <em>A survey of automated layout techniques for information presentations</em>, 2001. </p></li>
</ul>

<p>If you're more interested in the engineering aspects, you should look at Brad Myers' work (from the late 80s/early 90s) on the Garnet and Amulet toolkits. They have a TOPLAS paper, <a href="http://repository.cmu.edu/cgi/viewcontent.cgi?article=1761&amp;context=isr" rel="nofollow"><em>Lessons learned about one-way, dataflow constraints in the Garnet and Amulet graphical toolkits</em></a>, which summarizes what they learned.  </p>

CC BY-SA 3.0
2013-06-07T02:08:11.403Z
Great. Thanks! I've added those 3 items to the head of my research beam-search queue. I'll let you know how it goes.
Brandon Bloom
CC BY-SA 3.0
2013-06-05T19:56:09.860Z
2013-06-05T19:56:09.860Z
Neel Krishnaswami
<p>It's very common to view GUI layout as an optimization problem.</p>

<p>I've uncovered a lot of research around linear constraint systems, but a lot of real world layouts can not be represented linearly. For example, a simple "Wrapping" layout introduces discontinuities at line or column breaks.</p>

<p>Some real world systems compute layout recursively. They alternate between measuring and positioning widgets, then iterate until a fixed point. I've seen this process called "geometry negotiation" in the documentation for several of these widget libraries. However, I can not find any formal treatment of this approach.</p>

<p>Outside of linear constraints, are there any other formalisms targeted at these sorts of layout optimization systems?</p>

CC BY-SA 3.0
2013-06-05T05:07:16.317Z
Crazy stackexchange rules mean I need to put extra citations here: 
[2] http://menehune.opt.wfu.edu/Kokua/Irix_6.5.21_doc_cd/usr/share/Insight/library/SGI_bookshelves/SGI_Developer/books/XLib_WinSys/sgi_html/ch12.html

[3] http://www.qnx.com/developers/docs/6.5.0_sp1/index.jsp?topic=%2Fcom.qnx.doc.photon_prog_guide%2Fgeometry.html

[4] http://www.drdobbs.com/motif-geometry-management/184409755
Brandon Bloom
CC BY-SA 3.0
2013-06-05T16:36:42.330Z
what is the purpose? there are two other major schemes in applied software: html layout algorithms & also [java] swing layout algorithms. there are probably not more abstract analyses other than specs for those algorithms.
vzn
CC BY-SA 3.0
2013-06-05T17:58:43.400Z
HTML layout is derived from text and document layout systems. Widget layout is fundamentally different, hence the messy complexity of CSS layouts. Swing layout managers simply dictate layout to their children. As far as I know, Swing don't do any sort of negotiation with subcomponents, which seems necessary for more sophisticated layouts than those typically found in generic forms. The back and forth between components helps iterate to an optimized layout. Research into linear constraint layouts recognize the optimization nature of the problem, but preclude non-linear layouts.
Brandon Bloom
CC BY-SA 3.0
2013-06-05T18:45:52.587Z
I'm specifically asking for formal treatment in existing research of this category of problems. Isn't that, almost by definition, both research-level and theoretical? That other stack exchange site has less than half the number of users as this site (and is still in "beta"). Forgive me for not being an expert on stack exchange politics, but from the outside, it appears that my question is both perfectly appropriate and more likely to be answered here.
Brandon Bloom
CC BY-SA 3.0
2013-06-05T18:57:17.083Z
You didn't provide a link, so I found this: http://cstheory.stackexchange.com/helpcenter/on-topic -- After reading that, I still think my question falls within the scope of this site.
Brandon Bloom
CC BY-SA 3.0
2013-06-05T19:12:43.893Z
I edited it a bit. How's that?
Brandon Bloom
<linear-programming>
Research about geometry negotiation in widget layout
Brandon Bloom
# Research about geometry negotiation in widget layout

(Asked by: username_0 on 2013-06-05)

It's very common to view GUI layout as an optimization problem.

I've uncovered a lot of research around linear constraint systems, but a lot of real world layouts can not be represented linearly. For example, a simple "Wrapping" layout introduces discontinuities at line or column breaks.

Some real world systems compute layout recursively. They alternate between measuring and positioning widgets, then iterate until a fixed point. I've seen this process called "geometry negotiation" in the documentation for several of these widget libraries. However, I can not find any formal treatment of this approach.

Outside of linear constraints, are there any other formalisms targeted at these sorts of layout optimization systems?

**Tags:** linear-programming

> **Comments:**
> **username_0**: Crazy stackexchange rules mean I need to put extra citations here:  [2] http://menehune.opt.wfu.edu/Kokua/Irix_6.5.21_doc_cd/usr/share/Insight/library/SGI_bookshelves/SGI_Developer/books/XLib_WinSys/sgi_html/ch12.html  [3] http://www.qnx.com/developers/docs/6.5.0_sp1/index.jsp?topic=%2Fcom.qnx.doc.photon_prog_guide%2Fgeometry.html  [4] http://www.drdobbs.com/motif-geometry-management/184409755  
> **username_1**: what is the purpose? there are two other major schemes in applied software: html layout algorithms & also [java] swing layout algorithms. there are probably not more abstract analyses other than specs for those algorithms.  
> **username_0**: HTML layout is derived from text and document layout systems. Widget layout is fundamentally different, hence the messy complexity of CSS layouts. Swing layout managers simply dictate layout to their children. As far as I know, Swing don't do any sort of negotiation with subcomponents, which seems necessary for more sophisticated layouts than those typically found in generic forms. The back and forth between components helps iterate to an optimized layout. Research into linear constraint layouts recognize the optimization nature of the problem, but preclude non-linear layouts.  
> **username_0**: I'm specifically asking for formal treatment in existing research of this category of problems. Isn't that, almost by definition, both research-level and theoretical? That other stack exchange site has less than half the number of users as this site (and is still in "beta"). Forgive me for not being an expert on stack exchange politics, but from the outside, it appears that my question is both perfectly appropriate and more likely to be answered here.  
> **username_0**: You didn't provide a link, so I found this: http://cstheory.stackexchange.com/helpcenter/on-topic -- After reading that, I still think my question falls within the scope of this site.  
> **username_0**: I edited it a bit. How's that?  

---

## 1 answers

### Answer by username_2 on 2013-06-05. Score: 3

I would suggest looking at these survey papers and tracking down the citations in the bibliography, and digging up subsequent papers which cited these.

* Walter Hower, and Winfried Graf. *Research in constraint-based layout, visualization, CAD, and related topics : a bibliographical survey*, 1995.
* Simon Lok and Steven Feiner, *A survey of automated layout techniques for information presentations*, 2001.

If you're more interested in the engineering aspects, you should look at Brad Myers' work (from the late 80s/early 90s) on the Garnet and Amulet toolkits. They have a TOPLAS paper, [*Lessons learned about one-way, dataflow constraints in the Garnet and Amulet graphical toolkits*](http://repository.cmu.edu/cgi/viewcontent.cgi?article=1761&context=isr), which summarizes what they learned.

> **Comments:**
> **username_0**: Great. Thanks! I've added those 3 items to the head of my research beam-search queue. I'll let you know how it goes.  

---

